abcE-Xor Distance思维、拆位
题目
给出一颗带边权的树。求所有简单路径异或和。
解题思路
找任一结点x为根结点。记F(u,v)为u到v简单路径的异或值。
对于两个结点u,v,设w为uv的最近公共祖先,有
F(u,v)
= F(u,w) ^ F(w,v)
= F(u,w) ^ F(w,v) ^ F(x,w) ^ F(x,w)
= F(u,x) ^ F(x,v)
由于异或值每一位互不影响,因此可以拆位考虑。设$DP[i][j][k]$为子树中所有结点 到结点$i$、第$j$位、异或值为$k$的路径数。处理完$DP[root][j][k]$之后,对于每一位计算贡献,会产生贡献的路径分为两种,第一种
终点为root的路径,也就是$DP[root][j][1]$的数量
终点不为root的路径,取一个异或值为1的路径、一个异或值为0的路径,只有这时异或值还是1,会产生贡献。也就是$DP[root][j][0]\times DP[root][j][1]$
代码
1 |
|