[Medium] P6018 [Ynoi2010] Fusion tree

xiezheyuan2025/1/22约 1374 字大约 7 分钟

简要题意

你需要维护一个 $n$ 个点的树，点有点权，有 $m$ 次操作，支持：

1 x 将与点 $x$ 距离为 $1$ 的所有点的点权加上 $1$ 。
2 x v 将点 $x$ 的点权减去 $v$ 。
3 x 求所有与点 $x$ 距离为 $1$ 的所有点的点权的异或和。

$1\leq n,m\leq 5\times 10^5,0\leq a_i\leq 10^5$ 。

思路

我愿称此为 Ynoi Educational Round。

首先观察本题，我们大致可以对于每个点，将其所有子节点塞入到某一个数据结构中，这种数据结构需要支持修改一个数的值，全局所有数加上 $1$ ，查询所有数的异或和。

然后对于操作 $1$ ，我们先对 $x$ 的所有子节点全局加上 $1$ ，然后单独考虑父节点。为了方便后面的维护，我们给每个点记录一个标记，表示进行了多少次邻域加 $1$ 操作，然后就可以考虑父节点对祖父节点的结构的更新。

接着是操作 $2$ ，我们可以直接修改在父亲的结构中的值（记得考虑），操作 $3$ 先求出所有子节点的异或和，再考虑父节点即可。

现在的问题是，如何实现一个数据结构，支持修改一个数的值，全局所有数加上 $1$ ，查询所有数的异或和，我们考虑 01 trie。

但是我们通常建立的维护异或极值的 01 trie 似乎难以支持全局加 $1$ 这一操作。故我们考虑将每个数从低到高插入到 trie 中。

由于是按照从低到高插入的，因此也可以模拟全局加 $1$ 的从低到高进位。

具体地，由于 $0+1=1,1+1=(10)_2$ ，所以这一位相当于取反了，所以需要交换两个子树，然后原本的 $1$ 子树（现在的 $0$ 子树）受到进位影响，需要继续加 $1$ ，递归即可。时间复杂度显然为 $O(\log V)$ ，代码如下：

void update(int i){
    swap(trie[i][0], trie[i][1]);
    if(trie[i][0]) update(trie[i][0]);
    pushup(i);
}

然后我们需要同时维护异或和，这时我们模仿其他数据结构（线段树、平衡树等）的思想，采用将子节点的数据上推到父节点的方法，将所有数据上推到根节点，也就是喜闻乐见的 pushup。

记 $f_i$ 表示 01 trie 中以 $i$ 为根的子树所代表的 01 trie 的所有元素的异或和，那么考虑从子节点中转移，对于 $0$ 子节点的数据 $f_j$ ，只需要令 $f_i\gets 2f_j$ 即可。单数对于 $1$ 子节点就不一样，这一位的答案与子树的元素数量的奇偶性有关（如果为偶数，那么这一位就相消了），不妨再记录一个值，表示每个点储存的数的奇偶性，不难发现这样就可以正确求出 $f_i$ 了：

// 这里的 xort 是 f(i)，w 是奇偶性
void pushup(int i){
    xort[i] = w[i] = 0;
    if(trie[i][0]) xort[i] ^= (xort[trie[i][0]] << 1), w[i] ^= w[trie[i][0]];
    if(trie[i][1]) xort[i] ^= (xort[trie[i][1]] << 1) | w[trie[i][1]], w[i] ^= w[trie[i][1]];
}

至于修改一个元素的值，可以看成先删除后插入。由于 $x\oplus x=0$ ，所以删除一个数 $x$ 可以看成再插入一个 $x$ 来和之前的 $x$ 的贡献相消：

void insert(int x, int &i, int lvl=0){
    if(!i) i = ++tot;
    if(lvl > 30) return (w[i] ^= 1), void();
    insert(x >> 1, trie[i][x & 1], lvl + 1);
    pushup(i);
}

于是这道题就做完了。时间复杂度 $O(m\log V)$ 。

做完本题后可以去看看 P6623 [省选联考 2020 A 卷] 树，该题目同样也是 01 trie 维护异或和的应用，不过还要写 01 trie 合并，01 trie 合并与线段树合并类似，都是对应子树暴力合并信息：

int merge(int x, int y){
    if(!x || !y) return x | y;
    w[x] ^= w[y], xort[x] ^= xort[y];
    trie[x][0] = merge(trie[x][0], trie[y][0]), trie[x][1] = merge(trie[x][1], trie[y][1]);
    return x;
}

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5, N_ = 2e7 + 5;

int trie[N_][2], w[N_], xort[N_], tot;

void pushup(int i){
    xort[i] = w[i] = 0;
    if(trie[i][0]) xort[i] ^= (xort[trie[i][0]] << 1), w[i] ^= w[trie[i][0]];
    if(trie[i][1]) xort[i] ^= (xort[trie[i][1]] << 1) | w[trie[i][1]], w[i] ^= w[trie[i][1]];
}

void insert(int x, int &i, int lvl=0){
    if(!i) i = ++tot;
    if(lvl > 30) return (w[i] ^= 1), void();
    insert(x >> 1, trie[i][x & 1], lvl + 1);
    pushup(i);
}

void update(int i){
    swap(trie[i][0], trie[i][1]);
    if(trie[i][0]) update(trie[i][0]);
    pushup(i);
}

int n, m, father[N], a[N], tag[N];
vector<int> g[N];
int rt[N];

void dfs(int u, int fa){
    father[u] = fa;
    for(int v : g[u]){
        if(v == fa) continue;
        dfs(v, u);
        insert(a[v], rt[u]);
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1,u,v;i<n;i++){
        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, v; cin >> op >> x;
        if(op == 1){
            update(rt[x]), tag[x]++;
            int f = father[father[x]];
            if(f) insert(a[father[x]] + tag[f], rt[f]);
            if(father[x]) a[father[x]]++;
            if(f) insert(a[father[x]] + tag[f], rt[f]);
        }
        else if(op == 2){
            cin >> v;
            if(father[x]) insert(a[x] + tag[father[x]], rt[father[x]]);
            a[x] -= v;
            if(father[x]) insert(a[x] + tag[father[x]], rt[father[x]]);
        }
        else{
            int ans = xort[rt[x]];
            ans ^= (a[father[x]] + tag[father[father[x]]]);
            cout << ans << '\n';
        }
    }
    return 0;
}

// Written by xiezheyuan