解题思路
我们考虑操作的性质。每次操作选择一个节点 v 和一个非负整数 x,会将 v 的子树中所有与 v 距离为偶数的节点异或 x。
由于异或运算满足自反律(a⊕a=0),我们可以自底向上地处理整棵树,使得每个节点通过一次操作变为 0。
关键观察:对于任意节点 u,若其深度(到根节点 1 的距离)的奇偶性为 p=dmod2,则只有那些“所在操作节点与 u 距离为偶数”的操作才会影响 u,而这样的操作节点必须与 u 同奇偶性。也就是说,所有深度奇偶性与 u 相同的节点上施加的操作,都会对 u 产生异或影响。因此,我们可以维护两个累积异或值:
- cum[0]:表示到目前为止,对所有深度为偶数的节点所施加操作的累积异或;
- cum[1]:表示到目前为止,对所有深度为奇数的节点所施加操作的累积异或。