题解：CF1980G Yasya and the Mysterious Tree

yshpdyt · 2024-06-11 15:40:57 · 题解

题意

一棵有边权的树，存在两种操作：

1. ^ x ：所有边权异或 x。
2. ? v x ：新建一条一端为 v 边权为 x 的边，你可以选择不为 v 的任意点 u 作为边的另一端 ，最大化在环上的边的边权异或和。

操作 1 保留，操作 2 保留。

Sol

疑惑题！

先不管修改操作。

把一个环分成三部分，lca\rightarrow x，lca\rightarrow y，x\rightarrow y。

为了方便表示，记 f_{x,y} 表示以 x,y 作为两端的链上边权异或和。

如果多组询问每次给定 x,y,val，即在 x,y 间新建边权为 val 的边，统计答案是简单的，考虑类似树上差分的操作，具体来说有：

所以维护每个点到根节点路径上边权异或和即可求解。

现在 x 变成未知的，仍然考虑上面的式子，只有 f_{x,root} 发生改变，不妨把所有 f_{x,root} 拉出来弄成序列，右边两个定值设为 d，问题转化成对于给定的 d，选择序列中的一个数，让异或的结果最大，这是很典的套路，用 01trie 可以轻松维护。

具体来说，把所有 f_{x,root} 放入 01trie，对于查询 y,val，由于 x\neq y，先把 f_{y,root} 踢出字典树，然后直接查询即可。

现在考虑带修改如何做，如果只修改一条边的话会变得很复杂（也许是我太菜了），但是题目要的是全局异或，这就很容易了，可以类似懒标记给全局打 tag 并且标记永久化，设异或值为 k。

我们只关心一个点到根节点的异或和，设根节点深度为 1，一个点的深度为 dep_x，修改后需要异或 dep_x-1 次 k，由于异或的性质，相当于偶数深度节点的答案异或，而奇数深度节点不异或，每次修改操作的都是同一批点，所以我们可以记录 k=\bigoplus\limits_{i=1}^{m}k_i，表示至今所有修改操作的异或和。

由于深度为奇数的点不需要异或，而偶数的点需要，考虑建两颗 01trie，分别在奇数树和偶数树上以不同的异或值查找。

具体来说，经过修改后当前节点到根节点的路径异或和为 w=f_{x,root}\oplus\left(k\times[dep_x\equiv0\pmod2]\right)，在奇数树上查异或 w\oplus val 的最大值，在偶数树上查异或 w\oplus val\oplus k 的最大值。

本题充分使用了异或的交换律。

时间复杂度 O(n \log n)。

Code

#include<bits/stdc++.h>
#define ll long long
#define N 200005
#define endl "\n" 
#define fi first
#define se second
using namespace std;
const ll mod=1e9+7;
const ll inf=1e18;
const double eps=1e-6;

vector<pair<ll,ll> >v[N];
ll x2[35];
ll n,m;
struct trie{
    ll cnt,tr[N*34][2],rt,num[N*34];
    void ins(ll &p,ll x,ll d){
        if(!p)p=++cnt;
        num[p]++;
        if(d<0)return ;
        if((x>>d)&1)ins(tr[p][1],x,d-1);
        else ins(tr[p][0],x,d-1);
    }
    ll qr(ll p,ll x,ll d){
        if(d<0)return 0;
        ll t=(x>>d)&1;
        if(tr[p][t^1])return x2[d]+qr(tr[p][t^1],x,d-1);
        return qr(tr[p][t],x,d-1);
    }
    void del(ll &p,ll x,ll d){
        num[p]--;
        if(d<0){
            if(num[p]==0)p=0;
            return ;
        }
        if((x>>d)&1)del(tr[p][1],x,d-1);
        else del(tr[p][0],x,d-1);
        if(num[p]==0)p=tr[p][1]=tr[p][0]=0;
    }
}T[2];
ll dep[N],f[N];
void dfs(ll x,ll fa){
    dep[x]=dep[fa]+1;
    T[dep[x]&1].ins(T[dep[x]&1].rt,f[x],33);
    for(auto [y,val]:v[x]){
        if(y==fa)continue;
        f[y]=f[x]^val;
        dfs(y,x);
    }
}
void sol(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        ll x,y,z;
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    dfs(1,0);
    ll k=0;
    for(int i=1;i<=m;i++){
        char c;
        ll x,val;
        cin>>c;
        if(c=='^'){
            cin>>val;
            k^=val;
        }else{
            cin>>x>>val; 
            T[dep[x]&1].del(T[dep[x]&1].rt,f[x],33);
            ll w=((dep[x]&1)?f[x]:(f[x]^k));
            ll p=max(T[0].qr(T[0].rt,w^val^k,33),T[1].qr(T[1].rt,w^val,33));
            cout<<p<<" ";
            T[dep[x]&1].ins(T[dep[x]&1].rt,f[x],33);
        }
    }
    for(int i=1;i<=n;i++){
        v[i].clear();
        T[dep[i]&1].del(T[dep[i]&1].rt,f[i],33);
    }
    T[1].cnt=T[0].cnt=0;
    cout<<endl;
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    x2[0]=1;
    for(int i=1;i<=33;i++)x2[i]=x2[i-1]*2;
    ll ttt;
    cin>>ttt;
    while(ttt--)sol();
    return 0;
}