最大节点价值之和

100210. 最大节点价值之和

给你一棵 n 个节点的无向树，节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你，其中 edges[i] = [u_i, v_i] 表示树中节点 u_i 和 v_i 之间有一条边。同时给你一个正整数 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⁴
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 构成一棵合法的树。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) { } };

golang 解法, 执行用时: 124 ms, 内存消耗: 8.6 MB, 提交时间: 2024-03-06 09:43:51

func maximumValueSum(nums []int, k int, _ [][]int) int64 {
	f0, f1 := 0, math.MinInt
	for _, x := range nums {
		f0, f1 = max(f0+x, f1+(x^k)), max(f1+x, f0+(x^k))
	}
	return int64(f0)
}

func maximumValueSum2(nums []int, k int, edges [][]int) int64 {
	n := len(nums)
	g := make([][]int, n)
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}

	var dfs func(int, int) (int, int)
	dfs = func(x, fa int) (int, int) {
		f0, f1 := 0, math.MinInt // f[x][0] 和 f[x][1]
		for _, y := range g[x] {
			if y != fa {
				r0, r1 := dfs(y, x)
				f0, f1 = max(f0+r0, f1+r1), max(f1+r0, f0+r1)
			}
		}
		return max(f0+nums[x], f1+(nums[x]^k)), max(f1+nums[x], f0+(nums[x]^k))
	}
	ans, _ := dfs(0, -1)
	return int64(ans)
}

python3 解法, 执行用时: 112 ms, 内存消耗: 24.4 MB, 提交时间: 2024-03-06 09:43:02

class Solution:
    # 树形dp
    def maximumValueSum1(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        g = [[] for _ in nums]  # 邻接矩阵
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        def dfs(x: int, fa: int) -> (int, int):
            f0, f1 = 0, -inf  # f[x][0] 和 f[x][1]
            for y in g[x]:
                if y != fa:
                    r0, r1 = dfs(y, x)
                    f0, f1 = max(f0 + r0, f1 + r1), max(f1 + r0, f0 + r1)
            return max(f0 + nums[x], f1 + (nums[x] ^ k)), max(f1 + nums[x], f0 + (nums[x] ^ k))
        return dfs(0, -1)[0]

    # 状态机dp
    def maximumValueSum(self, nums: List[int], k: int, _: List[List[int]]) -> int:
        f0, f1 = 0, -inf
        for x in nums:
            f0, f1 = max(f0 + x, f1 + (x ^ k)), max(f1 + x, f0 + (x ^ k))
        return f0

上一题

下一题

详情