3068. 最大节点价值之和

发表于 2025-12-16 分类于力扣阅读次数： Waline：本文字数： 1.4k 阅读时长 ≈ 5 分钟

考点

状态机DP
贪心

思路

一、问题概述与核心难点

给定一棵含 \(n\) 个节点的树，每个节点 \(i\) 具有权值 \(a_i\)。允许进行如下操作任意多次：

选择一条边 \((u,v)\)
同时对两个端点执行 \[ a_u \leftarrow a_u \oplus k,\quad a_v \leftarrow a_v \oplus k \]

目标是在任意操作序列后，使所有节点权值之和最大。

表面特征与真实本质的冲突

表面特征：操作定义在“树的边”上，直觉上容易联想到：
- 树形 DP
- 子树状态合并
- 父子节点的相互影响
真实本质：树结构并不参与数值优化过程，而仅用于保证一个可达性约束。

理解这一点，是本题的核心突破。

二、从“树操作”到“全局奇偶约束”的等价转化

1. 操作的两个基本性质

一次操作具有以下不可变特性：

每次操作必然翻转两个节点
不存在“只翻转一个节点”的合法操作

因此： \[ \text{最终被 XOR 的节点数} \equiv 0 \pmod{2} \] 即：被翻转节点的数量必须为偶数。

2. 树结构的唯一作用：可达性保证

在一棵树中，任意两点之间路径唯一。

关键结论：

对任意两个节点 \(u, v\)，沿它们之间的唯一路径，依次对路径上的每一条边执行操作，则：

路径中间节点被翻转 2 次（抵消）

仅有端点 \(u, v\) 各被翻转 1 次

因此：

在树上，任意一对节点都可以被“单独翻转”而不影响其他节点。

3. 推论：任意偶数个节点都可被独立翻转

若选择的节点集合大小为偶数
可将其两两配对
对每一对沿路径操作

最终效果是：

目标节点各翻转一次
非目标节点翻转次数为偶数 → 不变

4. 结论（问题等价）

原问题 等价于：

给定数组 \(a_1,\dots,a_n\)，对任意 偶数个位置 执行 \[ a_i \leftarrow a_i \oplus k \] 使总和最大。

此时：

树结构已不再参与优化
问题退化为一个全局子序列选择问题

三、收益建模：从“翻不翻”到数值优化

对每个节点定义： \[ \text{gain}_i = (a_i \oplus k) - a_i \] 含义：

若不翻转节点 \(i\)，收益为 0
若翻转节点 \(i\)，总和增加 \(\text{gain}_i\)

问题转化为：

从所有 \(\text{gain}_i\) 中选取一个 偶数大小的子集，使收益之和最大。

四、解法一：贪心 + 奇偶修正

4.1 基本贪心策略

所有 \(\text{gain}_i > 0\) 的节点必选
因为单独选择即可增加总和

设：

\(S = \sum a_i\)：原始总和
\(D = \sum_{\text{gain}_i>0} \text{gain}_i\)
\(cnt\)：正收益节点个数

4.2 奇偶性冲突

若 \(cnt\) 为偶数： \[ \text{答案} = S + D \]
若 \(cnt\) 为奇数：违反“翻转数必须为偶数”的约束

4.3 两种合法修正方案

必须在以下两种方案中取最大值：

方案 A：删除一个最小正收益

令 \[ m^+ = \min\{\text{gain}_i \mid \text{gain}_i > 0\} \]
新收益： \[ S + D - m^+ \]

方案 B：补充一个最大非正收益

令 \[ m^- = \max\{\text{gain}_i \mid \text{gain}_i \le 0\} \]
新收益： \[ S + D + m^- \]

4.4 最终答案

\[ \boxed{ \text{ans} = \begin{cases} S + D, & cnt \equiv 0 \pmod{2} \\ \max(S + D - m^+,\, S + D + m^-), & cnt \equiv 1 \pmod{2} \end{cases} } \]

4.5 AC代码

class Solution {
public:
    const long long neg = LLONG_MIN >> 1;
    const long long inf = LLONG_MAX >> 1;

    long long maximumValueSum(vector<int>& nums, int k,
                              vector<vector<int>>& edges) {
        long long s = 0;      // 原始总和 S
        long long d = 0;      // 所有正收益之和 D
        int time = 0;         // 正收益节点个数
        long long mi = neg;   // 最大的非正 gain (m^-)
        long long mx = inf;   // 最小的正 gain (m^+)

        for (int x : nums) {
            long long gain = (x ^ k) - x;
            s += x;

            if (gain > 0) {
                d += gain;
                ++time;
                mx = min(mx, gain);
            } else {
                mi = max(mi, gain);
            }
        }

        // 奇偶性修正
        if (time & 1) {
            return max(s + d + mi, s + d - mx);
        }
        return s + d;
    }
};

五、解法二：状态机 DP（even / odd）

5.1 状态定义

设： \[ f[i][0] = \text{处理前 } i \text{ 个节点，翻转数为偶数的最大和} \]

5.2 初始状态

\[ f[0][0] = 0,\quad f[0][1] = -\infty \]

表示尚未处理任何节点，只能处于“偶数翻转”状态。

5.3 状态转移方程

对第 \(i\) 个节点，值为 \(x\)：

不翻转：奇偶性不变
翻转：奇偶性取反

\[ \begin{aligned} f[i][0] &= \max\big(f[i-1][0] + x,\; f[i-1][1] + (x \oplus k)\big) \\ f[i][1] &= \max\big(f[i-1][1] + x,\; f[i-1][0] + (x \oplus k)\big) \end{aligned} \]

5.4 最终答案

\[ \boxed{f[n][0]} \]

必须是偶数次翻转。

5.5 AC代码

class Solution {
public:
    const long long neg = LLONG_MIN >> 1;

    long long maximumValueSum(vector<int>& nums, int k,
                              vector<vector<int>>& edges) {
        int n = nums.size();
        static long long f[20005][2];

        f[0][0] = 0;
        f[0][1] = neg;

        for (int i = 1; i <= n; ++i) {
            long long x = nums[i - 1];
            f[i][0] = max(f[i - 1][0] + x,
                          f[i - 1][1] + (x ^ k));
            f[i][1] = max(f[i - 1][1] + x,
                          f[i - 1][0] + (x ^ k));
        }
        return f[n][0];
    }
};

六、两种解法的统一视角

贪心解法： 先假设“全部翻正收益” → 再修正奇偶冲突
DP 解法： 在决策过程中显式维护奇偶状态

二者在数学意义上完全等价，区别仅在实现方式。

七、总结

本题并非树形 DP
树结构只用于证明：

任意偶数个节点都可被独立翻转
真正的优化问题是一个：
- 带“偶数约束”的子序列选择问题
贪心与状态机 DP 是该问题的两种等价解法