注意到异或和加法有着非常相似的性质——只有异或运算时,顺序并不影响结果。因此我们完全可以把两类操作分开处理。
对于子树异或操作,我们可以记录下来某个节点的所有操作的异或和,然后在最后进行一次 DFS,DFS 过程中记录根到当前节点路径上的节点的操作的异或和,然后异或到当前节点权值上即可。
对于到根路径的异或操作,我们同样可以记录每个节点的操作异或和,然后最后进行一次另一种 DFS,DFS 过程中统计子树内的节点的操作异或和,并异或到当前节点上,再把这个异或和作为返回值传给上一层节点即可。
总复杂度 O(n)O(n)O(n)。
使用您的 Hydro 通用账户