考虑一棵从低位到高位的 Trie.
每次全局加一，末位是 \(0\) 的数，末位会变成 \(1\)；其他数，末位会变成 \(0\) 然后向前进位。
考虑直接交换左右子树，然后要进位的是交换后左子树的点，递归处理就行。
注意原来在节点 \(u\) 结束的数也会因为 \(+1\) 全部进入右子树，需要处理一下，可以参照代码理解。
由于每次只会递归一个子树，全局 \(+1\) 的复杂度是 \(O(\log V)\).
#include <bits/stdc++.h>
using namespace std;#define int long long
const int N = 525015, M = N * 25 + 5;int n, a[N], p, ch[M][2], tot, val[M], ans, root[N];
bool siz[M], ed[M];
vector<int> g[N];void pushup(int p)
{siz[p] = (ed[p] ^ siz[ch[p][0]] ^ siz[ch[p][1]]);val[p] = ((val[ch[p][0]] << 1) ^ ((val[ch[p][1]] << 1) | siz[ch[p][1]]));
}void insert(int &p, int k)
{if(!p) p = ++tot;if(!k) return (void) (ed[p] ^= 1, siz[p] ^= 1);insert(ch[p][k & 1], k >> 1);pushup(p);
}void modify(int p) // 全局 +1
{if(!p) return;swap(ch[p][0], ch[p][1]);if(ed[p] && !ch[p][1]) ch[p][1] = ++tot;ed[ch[p][1]] ^= ed[p], siz[ch[p][1]] ^= ed[p];ed[p] = 0;modify(ch[p][0]);pushup(p);return;
}void merge(int &x, int &y)
{if(!y) return;if(!x) return (void) (x = y);ed[x] ^= ed[y];val[x] ^= val[y];siz[x] ^= siz[y];merge(ch[x][0], ch[y][0]);merge(ch[x][1], ch[y][1]);pushup(x);return;
}void dfs(int u, int fa)
{for(auto v : g[u])if(v != fa) dfs(v, u), merge(root[u], root[v]);modify(root[u]);insert(root[u], a[u]);ans += val[root[u]];return;
}signed main()
{ios :: sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 2; i <= n; i++)cin >> p, g[p].push_back(i);dfs(1, 0);cout << ans;return 0;
}
其实还有全局 -1，维护方法是类似的。
例题是洛谷 P14509 树上求值。不过这题的贡献和位数有关，所以还要多记录一个 trie 树上的深度。
void pushup(int p, int h)
{val[p] = (val[ch[p][0]] * a[0][h] % m + val[ch[p][1]] * a[1][h] % m) % m;
}void insert(int &p, int k, int h)
{if(!p) p = ++tot;// cout << (k & 1);if(h > 20) return (void) (val[p]++);insert(ch[p][k & 1], k >> 1, h + 1);pushup(p, h);return;
}void modify(int p, int h) // 全局 -1
{if(!p) return;swap(ch[p][0], ch[p][1]);modify(ch[p][1], h + 1);pushup(p, h);return;
}void merge(int &x, int &y, int h)
{if(!y) return;if(!x) return (void) (x = y);val[x] += val[y]; val[x] %= m;if(h > 20) return;merge(ch[x][0], ch[y][0], h + 1);merge(ch[x][1], ch[y][1], h + 1);pushup(x, h);return;
}