CF766E Mahmoud and a xor trip 题解
提供一种有点复杂但是好想的换根 dp 思路，好像没什么人写。
给定一棵树，带点权，设 \(I(i, j)\) 表示 \(i\) 到 \(j\) 的路径按位异或和，求：
拆位 & 状态
按位异或，先拆个位，每位单独考虑。（以下所写皆为只考虑其中一位时的做法。）
状态就是换根 dp 经典的两个数组：
-
\(s_{u,0/1}\) 表示，有多少 \(v \in \text{sub}_u\) 满足 \(I(u, v) = 0/1\)。（只考虑子树内的 \(v\)。）
-
\(f_{u,0/1}\) 表示，有多少 \(v\) 满足 \(I(u, v) = 0/1\)。（考虑所有 \(v \in [1,n]\)。）
\(s\) 转移
平凡的，其中 \(b\in\{0,1\}\)：
（最后那个 \([a_u = b]\) 就是 \(I(u, u) = b\) 的情况，我们由子树转移来的时候没有统计到。）
\(f\) 转移
至于 \(f\) 的转移，我是胡了个大分讨，有无大佬优化下qwq：（\(v\in\operatorname{son}_u\)）
- \(a_u = 0\)，\(a_v = 0\)：
珂以画图看一下，对于所有节点 \(x\)，\(I(x, u) = I(x, v)\)，因此 \(f_{v, 0} = f_{u, 0}\)，\(f_{v, 1} = f_{u, 1}\)。
- \(a_u = 1\)，\(a_v = 1\)：
与上面相反，对于节点 \(x\)，\(I(x, u) = \neg\ I(x, v)\)，因此 \(f_{v, 0} = f_{u, 1}\)，\(f_{v, 1} = f_{u, 0}\)。
- \(a_u = 1\)，\(a_v = 0\)：
对于 \(v\) 子树外的节点 \(x\)，\(I(x, u) = I(x, v)\)。
而对于 \(v\) 子树内的节点 \(x\)，\(I(x, u) = \neg\ I(x, v)\)。
（第一个括号是子树外，第二个括号是子树内）
\(f_{v, 0} = (f_{u, 0} - s_{v, 1}) + (s_{v, 0})\)
\(f_{v, 1} = (f_{u, 1} - s_{v, 0}) + (s_{v, 1})\)
- \(a_u = 0\)，\(a_v = 1\)：
与上面相反。
对于 \(v\) 子树外的节点 \(x\)，\(I(x, u) = \neg\ I(x, v)\)。
而对于 \(v\) 子树内的节点 \(x\)，\(I(x, u) = I(x, v)\)。
\(f_{v, 0} = (f_{u, 1} - s_{v, 1}) + (s_{v, 0})\)
\(f_{v, 1} = (f_{u, 0} - s_{v, 0}) + (s_{v, 1})\)
统计答案
\(lg\) 是当前考虑第几位，从 \(0\) 开始。\(V\) 是值域。
对于每个点，求出所有以它为端点的路径答案之和。这样每条路径会算两次，因此最后除以 \(2\)。
但是，仅包含一个点的路径只会被算一次！！！所以把它们再加一遍，保证除以 \(2\) 的时候不出错。
做完了。这个做法确实挺麻烦，但是感觉比较直观。