1 条题解

  • 0
    @ 2026-11-15 20:48:16

    题目分析

    注意到异或和加法有着非常相似的性质——只有异或运算时,顺序并不影响结果。因此我们完全可以把两类操作分开处理。

    对于子树异或操作,我们可以记录下来某个节点的所有操作的异或和,然后在最后进行一次 DFS,DFS 过程中记录根到当前节点路径上的节点的操作的异或和,然后异或到当前节点权值上即可。

    对于到根路径的异或操作,我们同样可以记录每个节点的操作异或和,然后最后进行一次另一种 DFS,DFS 过程中统计子树内的节点的操作异或和,并异或到当前节点上,再把这个异或和作为返回值传给上一层节点即可。

    总复杂度 O(n)O(n)。

    • 1

    信息

    ID
    183
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者