省选题解第一发～
【省选联考2020】树
我和这道题还挺有缘分的。
有一次看大佬的省选游记（不知道是哪一年），然后提到有一道是01trie整体加一，当时我就印象深刻，然后在 oiwiki 上看了一下，心想这整体加一也只能从低位到高位维护 01trie 啊，又不能查询最大值，有什么卵用（划掉）。
这是两周前的事了，今天开始备战省选，做做真题，没想到点开，想了想发现就是这道题，那真是太巧了。这道题也融合了 01trie 的其他套路，我们来看一看。
题意
给定一棵 \(n\) 个结点的有根树 \(T\)，结点从 \(1\) 开始编号，根结点为 \(1\) 号结点，每个结点有一个正整数权值 \(v_i\)。
设 \(x\) 号结点的子树内（包含 \(x\) 自身）的所有结点编号为 \(c_1,c_2,\dots,c_k\)，定义 \(x\) 的价值为：
\( val(x)=(v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k, x)) \)
其中 \(d(x,y)\) 表示树上 \(x\) 号结点与 \(y\) 号结点间唯一简单路径所包含的边数，\(d(x, x) = 0\)。\(\oplus\) 表示异或运算。
\(1\leq n,v_i \leq 525010\)，\(1\leq p_i\leq n\)。
题解
不难看出，每一个 \(i\) 子树内节点的贡献从 \(i\) 到 \(fa_i\) 只加了一，然后再额外算上 \(fa_i\) 的贡献，\(val_{fa_i}\) 就是所有贡献的异或和。
所以重点在于维护异或和。
但是我们其实能维护异或和的东西很少，因为有区间加法，我们只能一位一位地维护，维护每一位 1 个数的奇偶性。
这时候我们解决两个问题：儿子信息合并到父亲去，维护能够全局加一的异或和，。而它们其实都指向了一个数据结构——01trie。（概念可以查询 https://oi-wiki.org/string/trie/）
01trie 合并
把子树合并到父亲，自然就是 01trie 合并。由于 01trie 本身就是动态开点权值线段树的变种，合并也不在话下，直接照抄线段树合并代码，甚至还更简单。
int merge(int p, int q, int dep) {
if (!p || !q) return p + q; //如果一个节点为空，直接返回另一个
if (dep != H + 1) {
//递归合并
ch[p][0] = merge(ch[p][0], ch[q][0], dep + 1);
ch[p][1] = merge(ch[p][1], ch[q][1], dep + 1);
}
cnt[p] += cnt[q];// 由于维护的是节点信息，而不是传统线段树维护的子树信息，直接加上去就好；
return p;
}
线段树（01trie）合并的时间复杂度特别奇妙，看似十分暴力，但是每次递归都会删去一个 \(q\) 点（合并上去，不利用其信息），总节点数是 \(n \log n\)，时间复杂度也是 \(O(n \log n)\)。
还有，我们这里没有维护全局异或和，因为我们进行了子树的拼接，而且不能遍历整棵树，维护很困难。但是这也没关系，直接把儿子的所有 \(val\) 异或起来就好了。
01trie全局加一
这是一个很经典也很巧妙的操作，也是 01trie 非寻常的用法。我们一般从高位到低位维护 01trie，因为这样可以查询异或最大k大什么什么的。但是在这个问题中，我们并不关心元素大小，只关心每一位的 0/1 情况，所以我们从低到高位建立 01trie，然后还需要维护当前节点被多少数经过。
这样有什么好处呢？就是全局加一，聪明的同学们应该很快就能想出来，加法是从低位开始加起，然后进位，符合建树顺序。如果我们要全局加一，对于第一层，0 全部变成 1，1 全部变成 0，后者还会进位，让它两个子树 0 变成 1，1 变成 0……
即对于当前节点，我们交换它的左右儿子，然后向 0 儿子跑，不断循环。在这个过程中就可以更新全局异或和，如果原来的 1 和当前的 1 个数之差为奇数，把 \(val_i\) 二进制对应位 xor 1。这样就可以了。
void add(int x) { //表示对树上节点 x 进行修改
int rt = x;
int p = top[x]; //top[x]表示x对应01trie的根
for (int i = 0; i <= H; i++) {
if (p == 0) return ;
if (abs(cnt[ch[p][1]] - cnt[ch[p][0]]) & 1) now[rt][i] = now[rt][i] ^ 1; //now是当前树上节点x答案，按照上述说法维护
swap(ch[p][1], ch[p][0]);
p = ch[p][0];
}
}
01trie插入
最后，留下了一个最简单的操作，我们只要把 \(i\) 插入到 01trie 里，就结束了！
当然，也不用在插入中维护答案，直接异或即可。
代码
我使用了 bitset 对二进制快速维护修改，十分简洁易懂。
int n;
vector<int> g[N];
int top[N], a[N], tot, ch[N * H][2];
int cnt[N * H];
ll ans;
bitset<H + 5> now[N];
int insert(int x, int p) {
if (p == 0) p = ++tot;
int rt = p;
for (int i = 0; i <= H; i++) {
cnt[p]++;
bool b = (x >> i) & 1;
if (!ch[p][b]) ch[p][b] = ++tot;
p = ch[p][b];
}
return rt;
}
int merge(int p, int q, int dep) {
if (!p || !q) return p + q;
if (dep != H + 1) {
ch[p][0] = merge(ch[p][0], ch[q][0], dep + 1);
ch[p][1] = merge(ch[p][1], ch[q][1], dep + 1);
}
cnt[p] += cnt[q];
return p;
}
void add(int x) {
int rt = x;
int p = top[x];
for (int i = 0; i <= H; i++) {
if (p == 0) return ;
if (abs(cnt[ch[p][1]] - cnt[ch[p][0]]) & 1) now[rt][i] = now[rt][i] ^ 1;
swap(ch[p][1], ch[p][0]);
p = ch[p][0];
}
}
void solve(int u) {
for (int v : g[u]) {
solve(v);
top[u] = merge(top[u], top[v], 0);
now[u] ^= now[v];
}
add(u);
top[u] = insert(a[u], top[u]);
now[u] ^= a[u];
ans += now[u].to_ullong();
}
int main() {
//省略
solve(1);
return 0;
}