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\) 的时候不出错。
做完了。这个做法确实挺麻烦,但是感觉比较直观。