leetcode 3068. 最大节点价值之和【树形dp】

原题链接：3068. 最大节点价值之和

题目描述：

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

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

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

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

输入输出描述：

示例 1：

输入：nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
输出：6
解释：日增哥哥可以通过一次操作得到最大价值和 6 ：
- 选择边 [0,2] 。nums[0] 和 nums[2] 都变为：1 XOR 3 = 2 ，数组 nums 变为：[1,2,1] -> [2,2,2] 。
所有节点价值之和为 2 + 2 + 2 = 6 。
6 是可以得到最大的价值之和。

示例 2：

输入：nums = [2,3], k = 7, edges = [[0,1]]
输出：9
解释：日增哥哥可以通过一次操作得到最大和 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：

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

提示：

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

解题思路：

首先我们可以发现一个明显的性质就是每个结点位置的最终值和具体的操作次数没有关系，只和操作次数的奇偶性有关，当前位置i如果操作次数为奇数，那么当前位置值变为nums[i]^k,否则当前位置的值为nums[i]，此时状态就把一个非常大的无限空间的状态就缩小为了一个有限的搜索空间，就可以考虑dp了，dp的关键就在于怎么设计状态，通过上面分析我们可以知道只和操作次数的奇偶性有关，我们设计状态只需要设计奇偶性即可。

状态定义：

f[x][0]表示结点x操作偶数次时，子树x除去x的最大价值和

f[x][1]表示结点x操作奇数次时，子树x除去x的最大价值和

初始化：

对于每个结点，最开始操作次数为0，也就是为偶数，不可能奇数

所以f[x][0]=0,f[x][1]=负无穷

状态转移：

y是x的子节点，r0表示不操作x->y，r1表示操作x->y

r0=max(f[y][0]+nums[y],f[y][1]+(nums[y]^k))

r1=max(f[y][1]+nums[y],f[y][0]+(nums[y]^k))

f0=max(f0+r0,f1+r1)

f1=max(f1+r0,f0+r1)

最终答案：

最终答案就是根节点的r0,因为根节点没有父节点，所以答案就是r0

时间复杂度：O(n)，n为nums的长度。

空间复杂度：O(n)

cpp代码如下：

typedef long long LL;
class Solution {
public:
    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
        int n=nums.size();
        vector<vector<int>>g(n,vector<int>());
        for(auto& t:edges){
            int x=t[0],y=t[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        function<pair<LL,LL>(int,int)>dfs=[&](int x,int fa)->pair<LL,LL> {
            LL f0=0,f1=-1e18;
            for(auto& y:g[x]){
                if(y==fa)continue;
                auto [r0,r1]=dfs(y,x);
                LL t=max(f1+r0,f0+r1);
                f0=max(f0+r0,f1+r1);
                f1=t;
            }
            return pair{max(f0+nums[x],f1+(nums[x]^k)),max(f1+nums[x],f0+(nums[x]^k))};
        };

        return dfs(0,-1).first;
    }
};