P6018 Fusion tree

题面

原题链接 click

题解

如果放到 bfs 序下的话，其实就是区间加 \(1\)，单点修改，区间异或和。
区间加 \(1\) 和区间异或和不难想到反向的 01 Trie。
单点修改容易实现。
然后注意到这些“区间修改”的区间一定是一个结点的所有儿子构成的集合，对每个这种区间开一棵 Trie 维护即可。
时间复杂度 \(O(n\log a)\)，可以通过。

Code

#include<bits/stdc++.h>
using namespace std;
class trie{
    private:
    vector<int>t[2];
    int sz;
    vector<int>cnt;
    vector<int>ji,ou;
    int tj[20],to[20];
    public:
    trie(){
        t[1].clear();
        t[0].clear();
        cnt.clear();
        ji.clear();
        ou.clear();
        memset(tj,0,sizeof(tj));
        memset(to,0,sizeof(to));
        t[1].push_back(0);
        t[0].push_back(0);
        cnt.push_back(0);
        ji.push_back(0);
        ou.push_back(0);
        t[1].push_back(0);
        t[0].push_back(0);
        cnt.push_back(0);
        ji.push_back(0);
        ou.push_back(0);
        sz=1;
    }
    void insert(int x){
        int u=1;
        for(int i=0;i<=19;i++){
            int k=1<<i;
            if(x&k){
                ji[u]++;
                tj[i]++;
            }
            else{
                ou[u]++;
                to[i]++;
            }
            if(t[(x&k)>>i][u]==0){
                t[(x&k)>>i][u]=++sz;
                t[1].push_back(0);
                t[0].push_back(0);
                cnt.push_back(0);
                ji.push_back(0);
                ou.push_back(0);
            }
            u=t[(x&k)>>i][u];
        }
        cnt[u]++;
    }
    void erase(int x){
        int u=1;
        for(int i=0;i<=19;i++){
            int k=1<<i;
            if(x&k){
                ji[u]--;
                tj[i]--;
            }
            else{
                ou[u]--;
                to[i]--;
            }
            u=t[(x&k)>>i][u];
        }
        cnt[u]--;
    }
    void plusone(int u=1,int step=0){
        if(u==0) return;
        swap(t[0][u],t[1][u]);
        tj[step]-=ji[u];
        to[step]-=ou[u];
        swap(ji[u],ou[u]);
        tj[step]+=ji[u];
        to[step]+=ou[u];
        plusone(t[0][u],step+1);
    }
    int xorsum(){
        int ans=0;
        for(int i=0;i<=19;i++){
            ans+=(tj[i]&1)<<i;
        }
        return ans;
    }
}; 
int n,m;
vector<int>g[500005];
int a[500005];
int fa[500005];
trie t[500005];
int lazy[500005];
void dfs(int u,int f){
    fa[u]=f;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v!=f){
            dfs(v,u);
            t[u].insert(a[v]);
        }
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u); 
    }
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs(1,0);
    while(m--){
        int op,x,y;
        cin>>op;
        if(op==1){
            cin>>x;
            lazy[x]++;
            t[x].plusone();
            if(fa[x]==1) a[1]++;
            else{
                int v=fa[fa[x]];
                t[v].erase(a[fa[x]]+lazy[fa[fa[x]]]);
                a[fa[x]]++; 
                t[v].insert(a[fa[x]]+lazy[fa[fa[x]]]);
            }
        }else if(op==2){
            cin>>x>>y;
            if(x!=1) t[fa[x]].erase(a[x]+lazy[fa[x]]);
            a[x]-=y;
            if(x!=1) t[fa[x]].insert(a[x]+lazy[fa[x]]);

        }else{
            cin>>x;
            if(x==1) cout<<t[x].xorsum()<<endl;
            else if(g[x].size()==1) cout<<a[fa[x]]+lazy[fa[fa[x]]]<<endl;
            else cout<<((a[fa[x]]+lazy[fa[fa[x]]])^t[x].xorsum())<<endl;
        }
    }
    return 0;
}