题解 P3401 【洛谷树】

Created_equal1 · 2016-10-09 19:12:10 · 题解

方法1：

预处理每个点到根节点的xor值之后就变成了一个路径上任意两点xor的和，这个我们可以通过维护某一位是1的个数，然后分别统计贡献来做到。至于修改操作，就等价于一个子树某一位翻转修改。具体用树链剖分+线段树实现即可。

方法2：

考虑序列上的做法，我们可以用线段树维护一发左右子树的答案和每一位的情况来合并答案。把扔到树上去只要加上树链剖分即可。这种方法写起来比第一种方法麻烦一些。

两种做法的复杂度都是O(nlog^2n*w)的。