点击获取AI摘要

3068. 最大节点价值之和 H

给你一棵 n 个节点的 无向 树，节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你，其中 edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。同时给你一个 正 整数 k 和一个长度为 n 下标从 0 开始的 非负 整数数组 nums ，其中 nums[i] 表示节点 i 的 价值 。

Alice 想 最大化 树中所有节点价值之和。为了实现这一目标，Alice 可以执行以下操作 任意 次（包括 0 次）：

  • 选择连接节点 u 和 v 的边 [u, v] ，并将它们的值更新为：
    • nums[u] = nums[u] XOR k
    • nums[v] = nums[v] XOR k

请你返回 Alice 通过执行以上操作 任意次 后，可以得到所有节点 价值之和 的 最大值 。

示例 1：

示例1

输入：nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
输出：6
解释：Alice 可以通过一次操作得到最大价值和 6 ：

  • 选择边 [0,2] 。nums[0] 和 nums[2] 都变为：1 XOR 3 = 2 ，数组 nums 变为：[1,2,1] -> [2,2,2] 。
    所有节点价值之和为 2 + 2 + 2 = 6 。
    6 是可以得到最大的价值之和。

示例 2：

示例2

输入：nums = [2,3], k = 7, edges = [[0,1]]
输出：9
解释：Alice 可以通过一次操作得到最大和 9 ：

  • 选择边 [0,1] 。nums[0] 变为：2 XOR 7 = 5 ，nums[1] 变为：3 XOR 7 = 4 ，数组 nums 变为：[2,3] -> [5,4] 。
    所有节点价值之和为 5 + 4 = 9 。
    9 是可以得到最大的价值之和。

示例 3：

示例3

输入：nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
输出：42
解释：Alice 不需要执行任何操作，就可以得到最大价值之和 42 。

提示：

  • 2 <= n == nums.length <= 2 * 10⁴
  • 1 <= k <= 10⁹
  • 0 <= nums[i] <= 10⁹
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] <= n - 1
  • 输入保证 edges 构成一棵合法的树。

问题分析

给定一棵大小为 nn 的无向树，节点编号为 0,1,…,n−10,1,\dots,n-1，以及一个正整数 kk 和节点价值数组 nums[i]\text{nums}[i]。允许的操作是：任选一条边 [u,v][u,v]，对其两端的节点同时做一次 XORXOR 操作：

nums[u]←nums[u]⊕k,nums[v]←nums[v]⊕k.\text{nums}[u] \leftarrow \text{nums}[u] \oplus k,\quad \text{nums}[v] \leftarrow \text{nums}[v] \oplus k.

可以重复上述操作任意次。目标是最大化所有节点价值之和：

max⁡(∑i=0n−1nums[i]).\max\Bigl(\sum_{i=0}^{n-1} \text{nums}[i]\Bigr).

由于树上每次操作同时影响两个相邻节点，整个过程等价于对每个节点决定“最终是否被翻转奇数次”。记节点 ii 的最终状态位为 pi∈{0,1}p_i\in\{0,1\}，若 pi=1p_i=1 则节点 ii 的价值由 nums[i]↦nums[i]⊕k\text{nums}[i]\mapsto \text{nums}[i]\oplus k，否则保持不变。每条被选的边 e=(u,v)e=(u,v) 会让 pup_u 和 pvp_v 同时翻转一次，因此如果对边 ee 选择了奇数次，就相当于让 pup_u 与 pvp_v 最终状态异或一次。

  • 将这些约束在整棵树上传播，实际上对于树结构，可以定义一个根节点（取 00 号），并令每个节点状态由其子树的选择来决定。
  • 记对于子节点 vv，若整个以 vv 为根的子树中翻转为奇数的子边数为奇数，则子树在“奇偶”方面会有影响。需要合并所有子节点对当前节点的贡献。

故而可使用“树形 DP”解决：定义状态

dp[u][0]=以 u 为根，且 pu=0 时，子树贡献最大值,dp[u][1]=以 u 为根，且 pu=1 时，子树贡献最大值.dp[u][0] = \text{以 }u\text{ 为根，且 }p_u = 0\text{ 时，子树贡献最大值},\\ dp[u][1] = \text{以 }u\text{ 为根，且 }p_u = 1\text{ 时，子树贡献最大值}.

在对节点 uu 做 DFS 递归时，遍历所有子节点 vv，先计算其 dp[v][0],dp[v][1]dp[v][0],dp[v][1]，然后令该子树的基础贡献为

base_sum=∑v∈children(u)dp[v][0],\mathrm{base\_sum} = \sum_{v\in\mathrm{children}(u)} dp[v][0],

并收集每个子节点“若翻转 vv 的状态，相对于不翻转的增益”

Δv=dp[v][1]−dp[v][0].\Delta_v = dp[v][1] - dp[v][0].

把所有 Δv\Delta_v 分成正数类和负数类，用 sumPsumP 表示所有 Δv≥0\Delta_v\ge 0 的和，cntPcntP 表示 Δv≥0\Delta_v\ge 0 的数量，min⁡P\min P 表示正类中最小值，max⁡N\max N 表示负类中最大值。若选择令 uu 的子边翻转次数总体保持“偶数”，则贡献为

contrib_same=base_sum+sumP.\mathrm{contrib\_same} = \mathrm{base\_sum} + sumP.

否则（即翻转奇数次），需要从正类中去掉最小的 min⁡P\min P 或者从负类中加入最大的 max⁡N\max N，取更优，即

contrib_flip=max⁡( base_sum+(sumP−min⁡P), base_sum+(sumP+max⁡N)).\mathrm{contrib\_flip} = \max\bigl(\,\mathrm{base\_sum} + (sumP - \min P),\ \mathrm{base\_sum} + (sumP + \max N)\bigr).

然后根据 cntP mod 2cntP\bmod 2 来决定 uu 的子边翻转后与当前 pup_u 的奇偶如何匹配，依此更新 dp[u][0]dp[u][0] 与 dp[u][1]dp[u][1]。最终根节点 00 必须保证其 “父边不选” （即 p0=0p_0=0），答案即为 dp[0][0]dp[0][0]。

算法思路

  1. 建图与初始化

    • 用邻接表 gg 存储树结构。
    • 创建二维数组 dp[n][2]dp[n][2]，初始均为 00。

  2. DFS 递归

    • 对每个节点 uu，记录其父节点 parentparent，避免回溯。
    • 对所有子节点 v≠parentv \ne parent 递归调用 dfs(v, u)，获得 dp[v][0],dp[v][1]dp[v][0],dp[v][1]。
    • 计算子树基础贡献

      base_sum=∑vdp[v][0].\text{base\_sum} = \sum_{v} dp[v][0].

    • 列表 deltas 存储 Δv=dp[v][1]−dp[v][0]\Delta_v = dp[v][1] - dp[v][0]。
    • 按照 Δv\Delta_v 正负分组，计算：
      1
      2
      3
      4
      5
      sumP = ∑_{Δ_v ≥ 0} Δ_v
      cntP = |{v | Δ_v ≥ 0}|
      minP = min{Δ_v | Δ_v ≥ 0}  （若不存在正类则为 +∞）
      maxN = max{Δ_v | Δ_v < 0}   （若不存在负类则为 −∞）
      parityP = cntP mod 2
    • 计算两种子边翻转奇偶情况下的贡献：
      1
      2
      3
      4
      5
      contrib_same = base_sum + sumP
      contrib_flip = max(
        base_sum + (sumP - minP)    if cntP > 0,
        base_sum + (sumP + maxN)    if maxN > −∞
      )
    • 若 parityP == 0，则子边“偶数”对应 contrib_same，子边“奇数”对应 contrib_flip；否则相反。
    • 最后考虑 uu 自身是否翻转：
      • 对于 dp[u][0]dp[u][0]（pu=0p_u=0），若选择子翻转为“偶数”，则价值为 contribsame+nums[u]\mathrm{contrib_same} + \mathrm{nums}[u]；
        如果选择为“奇数”，则价值为 contribflip+(nums[u]⊕k)\mathrm{contrib_flip} + (\mathrm{nums}[u]\oplus k)。取两者最大。
      • 对于 dp[u][1]dp[u][1]（pu=1p_u=1），若子翻转为“偶数”，则价值为 contribsame+(nums[u]⊕k)\mathrm{contrib_same} + (\mathrm{nums}[u]\oplus k)；
        如果为“奇数”，则为 contribflip+nums[u]\mathrm{contrib_flip} + \mathrm{nums}[u]。同样取最大。

  3. 返回结果

    • 在根节点 00 上调用 dfs(0,−1)，最终 dp[0][0]dp[0][0] 即为整棵树在允许任意操作后能够获得的最大节点价值之和。

时间复杂度

  • 构建邻接表花费 O(n)O(n)。
  • DFS 过程对每个节点只访问一次，且对每个节点需要遍历其所有邻居并做常数时间的计算。合并子节点差值时，只做 O(deg⁡(u))O(\deg(u)) 次更新。
  • 整体每条边被访问两次，总共 O(n)O(n)。
  • 因此总时间复杂度为 O(n)\displaystyle O(n)，空间复杂度为 O(n)O(n)。

代码分解

  1. 图的表示与初始化
    1
    2
    3
    4
    5
    6
    n = len(nums)
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)
    dp = [[0, 0] for _ in range(n)]
  2. DFS 主逻辑函数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    def dfs(u, parent):
        base_sum = 0
        deltas = []
        for v in g[u]:
            if v == parent: continue
            dfs(v, u)
            base_sum += dp[v][0]
            deltas.append(dp[v][1] - dp[v][0])
        if not deltas:
            dp[u][0] = nums[u]
            dp[u][1] = nums[u] ^ k
            return
        sumP, cntP = 0, 0
        minP, maxN = float('inf'), -float('inf')
        for d in deltas:
            if d >= 0:
                sumP += d
                cntP += 1
                minP = min(minP, d)
            else:
                maxN = max(maxN, d)
        parityP = cntP % 2
        contrib_same = base_sum + sumP
        contrib_flip = -float('inf')
        if cntP > 0:
            contrib_flip = max(contrib_flip, base_sum + (sumP - minP))
        if maxN > -float('inf'):
            contrib_flip = max(contrib_flip, base_sum + (sumP + maxN))
        if parityP == 0:
            child_parity0 = contrib_same
            child_parity1 = contrib_flip
        else:
            child_parity1 = contrib_same
            child_parity0 = contrib_flip
        cand0_even = child_parity0 + nums[u]
        cand0_odd = child_parity1 + (nums[u] ^ k) if child_parity1 > -float('inf') else -float('inf')
        dp[u][0] = max(cand0_even, cand0_odd)
        cand1_even = child_parity0 + (nums[u] ^ k)
        cand1_odd = child_parity1 + nums[u] if child_parity1 > -float('inf') else -float('inf')
        dp[u][1] = max(cand1_even, cand1_odd)
  3. 调用与返回
    1
    2
    dfs(0, -1)
    return dp[0][0]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

class Solution:
    def maximumValueSum(self, nums, k, edges):
        n = len(nums)
        # 构建邻接表（无向树）
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)

        # dp[u][0]：以 u 为根的子树，且 “u 与父节点的边不被选” 时的最大贡献
        # dp[u][1]：以 u 为根的子树，且 “u 与父节点的边被选” 时的最大贡献
        dp = [[0, 0] for _ in range(n)]

        def dfs(u, parent):
            # 1. 先对所有子节点递归
            base_sum = 0   # 如果对 u 的所有子边都不选，子树的基础贡献 = sum(dp[v][0])
            deltas = []    # 每个 v 对应的增量 Δ = dp[v][1] - dp[v][0]
            for v in g[u]:
                if v == parent:
                    continue
                dfs(v, u)
                base_sum += dp[v][0]
                deltas.append(dp[v][1] - dp[v][0])

            # 2. 如果没有子节点，直接赋值
            if not deltas:
                dp[u][0] = nums[u]         # p_u = 0 时：u 取 nums[u]
                dp[u][1] = nums[u] ^ k     # p_u = 1 时：u 取 nums[u] ^ k
                return

            # 3. 划分 deltas 为正类/负类，同时统计 sumP, cntP, minP, maxN
            sumP = 0             # 所有 Δ >= 0 的和
            cntP = 0             # Δ >= 0 的个数
            minP = float('inf')  # 正类中最小的 Δ
            maxN = -float('inf') # 负类中最大的 Δ
            for d in deltas:
                if d >= 0:
                    sumP += d
                    cntP += 1
                    minP = min(minP, d)
                else:
                    maxN = max(maxN, d)

            parityP = cntP % 2
            # 当我们“保留所有正类”（不翻转奇偶）时的子树贡献：
            contrib_same = base_sum + sumP
            # 当我们想把“选中正类的个数”在原来奇偶上翻转一次时的子树贡献：
            #   A. 如果 cntP > 0，则可以从正类中去掉一个 minP => 贡献 = base_sum + (sumP - minP)
            #   B. 如果 maxN > -inf，则可以额外加一个 maxN => 贡献 = base_sum + (sumP + maxN)
            contrib_flip = -float('inf')
            if cntP > 0:
                contrib_flip = max(contrib_flip, base_sum + (sumP - minP))
            if maxN > -float('inf'):
                contrib_flip = max(contrib_flip, base_sum + (sumP + maxN))

            # 根据 cntP % 2，决定“子边被选的个数 mod 2 = 0”或“= 1”时的子树贡献
            if parityP == 0:
                # 当我们保留所有正类时，选中正类的个数 = cntP 为偶
                child_contrib_parity0 = contrib_same
                child_contrib_parity1 = contrib_flip
            else:
                # 当我们保留所有正类时，选中正类的个数 = cntP 为奇
                child_contrib_parity1 = contrib_same
                child_contrib_parity0 = contrib_flip

            # 4. 根据 p_u = 0 / 1，两种情况分别计算 dp[u][0]、dp[u][1]
            # ——————————————
            # 情况一：p_u = 0（u 与父边不选）
            #   如果子边选中个数 mod2 = 0: x_u = 0 => u 取 nums[u]
            cand0_even = child_contrib_parity0 + nums[u]
            #   如果子边选中个数 mod2 = 1: x_u = 1 => u 取 nums[u] ^ k
            if child_contrib_parity1 > -float('inf'):
                cand0_odd = child_contrib_parity1 + (nums[u] ^ k)
            else:
                cand0_odd = -float('inf')
            dp[u][0] = max(cand0_even, cand0_odd)

            # 情况二：p_u = 1（u 与父边选了）
            #   如果子边选中个数 mod2 = 0: x_u = 1 => u 取 nums[u] ^ k
            cand1_even = child_contrib_parity0 + (nums[u] ^ k)
            #   如果子边选中个数 mod2 = 1: x_u = 0 => u 取 nums[u]
            if child_contrib_parity1 > -float('inf'):
                cand1_odd = child_contrib_parity1 + nums[u]
            else:
                cand1_odd = -float('inf')
            dp[u][1] = max(cand1_even, cand1_odd)

        # 从根节点 0 开始 DFS
        dfs(0, -1)
        # 根节点没有父边，p_0 = 0
        return dp[0][0]

问题分析2

在任意次操作条件下，每条边选一次将使其端点同时做一次 XOR kXOR\,k。若我们将“最终节点 ii 被 XOR kXOR\,k 的次数模 2”记为状态 pi∈{0,1}p_i\in\{0,1\}，则每次对边 (u,v)(u,v) 的选择相当于对 (pu,pv)(p_u,p_v) 做一次异或操作。由于树的边集形成的线性系统有唯一约束：

∑i=0n−1pi≡0(mod2),\sum_{i=0}^{n-1} p_i \equiv 0 \pmod 2,

即最终被翻转奇数次的节点数必须为偶数（因为每条被选的边为两个端点各贡献一次翻转，总的翻转次数为偶数）。这样，问题就简化为：

在满足翻转节点数为偶数的约束下，决定哪些节点 ii 最终翻转，使得总价值

∑i=0n−1(nums[i]+pi⋅[(nums[i]⊕k)−nums[i]])\sum_{i=0}^{n-1} \bigl(\text{nums}[i] + p_i \cdot [(\text{nums}[i]\oplus k) - \text{nums}[i]]\bigr)

最大。

令每个节点 ii 的差值为

Δi  =  (nums[i]⊕k)  −  nums[i].\Delta_i \;=\; (\text{nums}[i]\oplus k)\;-\;\text{nums}[i].

若我们忽略约束，则只需对所有 Δi>0\Delta_i > 0 的节点都设 pi=1p_i=1；但由于必须保证 ∑ipi\sum_i p_i 为偶数，如果正差选取的数量为奇数，则需要“舍弃一个正差中最小的”或“额外加入一个负差中最大的”来翻转奇偶，取其中损失最小的一种。
因此，该方法不需要显式地做树形 DP，而是把所有节点看作“独立贡献”，只需一次扫描即可求得最优解。

算法思路2

  1. 计算差值数组
    对每个节点 ii，计算

    Δi=(nums[i]⊕k)−nums[i].\Delta_i = (\text{nums}[i]\oplus k) - \text{nums}[i].

  2. 求基础贡献
    若不做任何操作，则所有节点价值之和为

    base_sum  =  ∑i=0n−1nums[i].\mathrm{base\_sum} \;=\; \sum_{i=0}^{n-1} \text{nums}[i].

  3. 统计正负差值
    遍历所有 Δi\Delta_i：

    • 若 Δi≥0\Delta_i \ge 0，累加到 sumPsumP，并让 cntPcntP 自增；同时更新正类最小值 minPminP。
    • 否则（Δi<0\Delta_i < 0），更新负类最大值 maxNmaxN。

  4. 计算不翻转奇偶（偶数个正差）时的总贡献

    contrib_same=base_sum+sumP.\mathrm{contrib\_same} = \mathrm{base\_sum} + sumP.

    若此时 cntPcntP 已经是偶数，则该值即为最优。

  5. 若 cntPcntP 为奇数，需要翻转一次正负奇偶
    需要从“所有 Δi≥0\Delta_i\ge0 的集合”中去掉一个最小的，也就是

    drop_minP=base_sum+(sumP−minP).\mathrm{drop\_minP} = \mathrm{base\_sum} + (sumP - minP).

    或者向“Δi<0\Delta_i<0”的集合中再添入一个最大的负值，即

    add_maxN=base_sum+(sumP+maxN).\mathrm{add\_maxN} = \mathrm{base\_sum} + (sumP + maxN).

    令最终最优为

    max⁡(drop_minP, add_maxN).\max\bigl(\mathrm{drop\_minP},\ \mathrm{add\_maxN}\bigr).

  6. 返回结果
    返回上述最优值即可。

时间复杂度2

  • 计算 Δi\Delta_i 数组需 O(n)O(n)。
  • 统计正负、更新 sumPsumP, cntPcntP, minPminP, maxNmaxN 也需一次 O(n)O(n) 扫描。
  • 整体时间复杂度为 O(n)\displaystyle O(n)，空间复杂度为 O(n)O(n)（用于存储 Δ\Delta 数组）。

代码分解2

  1. 计算 Δi\Delta_i

    1
    deltas = [(num ^ k) - num for num in nums]

  2. 计算基础和

    1
    base_sum = sum(nums)

  3. 统计正负并维护最小正、最大负

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    sumP, cntP = 0, 0
    minP = float('inf')
    maxN = -float('inf')
    for delta in deltas:
        if delta >= 0:
            sumP += delta
            cntP += 1
            minP = min(minP, delta)
        else:
            maxN = max(maxN, delta)

  4. 计算 “不翻转奇偶” 时的贡献

    1
    2
    contrib_same = base_sum + sumP
    dp_root0 = contrib_same

  5. 若 cntPcntP 为奇数则做调整

    1
    2
    3
    4
    if cntP % 2 == 1:
        drop_minP = base_sum + (sumP - minP) if cntP > 0 else -float('inf')
        add_maxN = base_sum + (sumP + maxN) if maxN > -float('inf') else -float('inf')
        dp_root0 = max(drop_minP, add_maxN)

  6. 返回答案

    1
    return dp_root0

代码实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from heapq import heappush, heappop

class Solution:
    def maximumValueSum(self, nums, k, edges):
        # —— 1. 计算每个节点 i 的 Δ_i = (nums[i] ^ k) - nums[i]
        # 在树形 DP 里，我们把这叫做 deltas，当作 dp[v][1] - dp[v][0] 的简化版
        deltas = [(num ^ k) - num for num in nums]

        # —— 2. base_sum 对应“如果所有节点都不做任何 XOR k，那么基础贡献就是 sum(nums)”
        base_sum = sum(nums)

        # 接下来，用 sumP、cntP、minP、maxN 来合并所有 deltas
        sumP = 0               # 树形 DP 里记录“所有 Δ >= 0 的累加”
        cntP = 0               # 记录“Δ >= 0 的个数”
        minP = float('inf')    # 记录“Δ >= 0 中的最小值”（如果没正数，则保持 +inf）
        maxN = -float('inf')   # 记录“Δ < 0 中的最大值”（如果没负数，则保持 -inf）

        for delta in deltas:
            if delta >= 0:
                sumP += delta
                cntP += 1
                if delta < minP:
                    minP = delta
            else:
                if delta > maxN:
                    maxN = delta

        # —— 3. contrib_same 表示“不翻转正负奇偶”时的子（全）树贡献：
        #     在树形 DP 里，就是 base_sum + sumP
        contrib_same = base_sum + sumP

        # 把它先赋给 dp_root0（对应根节点 p_0 = 0 时，且子边选数 mod2 与 cntP 原本同偶的情况）
        dp_root0 = contrib_same

        # —— 4. 如果 cntP 是奇数，就要“翻转一次正负奇偶”：
        # 两个选项：删一个最小正(minP) 或 加一个最大负(maxN)
        if cntP % 2 == 1:
            # 方案 A：如果有正类，就删除 minP
            if cntP > 0:
                drop_minP_contrib = base_sum + (sumP - minP)
            else:
                drop_minP_contrib = -float('inf')

            # 方案 B：如果有负类，就加上 maxN
            if maxN > -float('inf'):
                add_maxN_contrib = base_sum + (sumP + maxN)
            else:
                add_maxN_contrib = -float('inf')

            # 在树形 DP 里，这两者对应“sumOdd”的两种计算方式，取更大
            dp_root0 = max(drop_minP_contrib, add_maxN_contrib)

        # —— 5. 返回最终结果 dp_root0（相当于整棵树的 dp[0][0]）
        return dp_root0
维度 方法一：树形 DP 方法二：全局贪心（基于差值）
核心思想 在树上做自底向上的 DP，维护每个节点翻转与不翻转两种状态的最优值，合并子节点差值时需考虑“奇偶翻转” 将所有节点视作“独立差值”，只需统计正差与负差的数量与极值，利用全局奇偶约束直接求解
约束来源 边选择会影响其相邻节点状态，需要在 DFS 中显式处理子树合并的“奇偶”关系 只需注意“被翻转节点数量必须为偶数”──一条全局约束，省去了树形结构的复杂递归
实现难度 需要写递归、合并子节点增益、维护正负差值的最小/最大值、考虑多种奇偶分支 只要一次扫描，代码简洁；无需建图或做 DFS
时间复杂度 O(n)O(n) O(n)O(n)
空间复杂度 O(n)O(n) （邻接表 + DP 数组） O(n)O(n) （差值数组 + 常数额外变量）
典型场景 当关注对每条边操作的奇偶传递，并扩展到“若树结构更复杂”时可推广 若只需考虑“翻转约束 ∑pi≡0(mod2)\sum p_i \equiv 0 \pmod{2} ”，且树是连通无环结构时最优
优势 能处理更一般的“子树方向性”DP，逻辑清晰；适合需要扩展到变体约束的情况 直接高效；只用一次扫描即可；易于理解与实现
劣势 代码复杂度高，容易出错；需要显式管理多种子情况与奇偶分支 只对“树”且仅含全局奇偶约束的特例适用；若约束更复杂则失效