列表

详情

2378. 选择边来最大化树的得分

给定一个 加权 树，由 n 个节点组成，从 0 到 n - 1。

该树以节点 0 为 根，用大小为 n 的二维数组 edges 表示，其中 edges[i] = [pari, weighti] 表示节点 pari 是节点 i 的 父 节点，它们之间的边的权重等于 weighti。因为根结点 没有 父结点，所以有 edges[0] = [-1, -1]。

从树中选择一些边，使所选的两条边都不 相邻，所选边的权值之 和 最大。

 

返回所选边的 最大 和。

注意:

 

示例 1:

输入: edges = [[-1,-1],[0,5],[0,10],[2,6],[2,4]]
输出: 11
解释: 上面的图表显示了我们必须选择红色的边。
总分是 5 + 6 = 11.
可以看出，没有更好的分数可以获得。

示例 2:

输入: edges = [[-1,-1],[0,5],[0,-6],[0,7]]
输出: 7
解释: 我们选择权值为 7 的边。
注意，我们不能选择一条以上的边，因为所有的边都是彼此相邻的。

 

提示:

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: long long maxScore(vector<vector<int>>& edges) { } };

golang 解法, 执行用时: 360 ms, 内存消耗: 76.4 MB, 提交时间: 2023-10-21 22:30:38 

func maxScore(edges [][]int) int64 {
	n := len(edges)
	children := make([][]int, n)
	for i, edge := range edges {
       if i ==0{
            continue
        }
		children[edge[0]] = append(children[edge[0]], i)
	}
	cache := map[int]int64{}
	var dp func(i, selected int) int64
	dp = func(i, selected int) int64 {
		if res, ok := cache[i*selected]; ok {
			return res
		}
		var ans int64
		var all []int64
		var sel []int64
		var sum int64
		for _, child := range children[i] {
			temp:=dp(child, -1)
			all = append(all, temp)
			sel = append(sel, dp(child, 1))
			sum += temp
		}
		ans = sum
		if selected !=1{
			for ii := 0; ii < len(all); ii++ {
				if sum -all[ii]+ sel[ii] + int64(edges[children[i][ii]][1]) > ans{
					ans = sum -all[ii]+ sel[ii] + int64(edges[children[i][ii]][1])
				}
			}
		}
		cache[i*selected] = ans
		return ans
	}
	return dp(0, -1)
}

cpp 解法, 执行用时: 420 ms, 内存消耗: 164.1 MB, 提交时间: 2023-10-21 22:30:18 

#define LL long long
#define pLL pair<LL,LL>
#define pii pair<int,int>
#define f first
#define s second
class Solution {
    int n;
    vector<vector<pii>> tree;
    LL max(LL x, LL y) {
        if(x > y) return x;
        return y;
    }
    pLL treeDP(LL x) {
        pLL ret = {0, 0}, temp;
        int diff = 0;
        for(int i = 0; i < tree[x].size(); i++) {
            temp = treeDP(tree[x][i].f);
            ret.s += max(temp.f, temp.s);
            diff = max(diff, tree[x][i].s + temp.s - max(temp.f, temp.s));
        }
        ret.f = ret.s + diff;
        return ret;
    }
public:
    long long maxScore(vector<vector<int>>& edges) {
        n = edges.size();
        tree = vector<vector<pii>>(n);

        for(int i = 1; i < n; i++) 
            tree[edges[i][0]].push_back({i, edges[i][1]});

        pLL res = treeDP(0);
        
        return max(res.f, res.s);
    }
};

java 解法, 执行用时: 114 ms, 内存消耗: 142 MB, 提交时间: 2023-10-21 22:29:27 

class Solution {
    private List<Map<Integer, Integer>> graph = new ArrayList<>();
    private long[] traverse(int node) {
        // choose, ignore = (选择以当前节点为终点的边 father->node 的分数，跳过以当前节点为终点的边 father->node 的分数)
        long choose = 0;
        long ignore = 0;
        List<Long> path = new ArrayList<>();
        for (int child : graph.get(node).keySet()) {
            // x, y = (选择 node->child 边的分数，不选择 node->child 的分数) = next[0], next[1]
            long[] next = traverse(child);
            // 如果选择 father->node，那么后续应该跳过 node->child，即选择 y 作为后续的得分
            choose += next[1];
            // 如果没有选择 father->node，则在全部子节点边中，可以有一条边 node->child(k) 被选中（得分为 x(k) + graph[node][child(k)]），其他的 node->child(i) 都应该跳过（得分为 y(k)）；怎么样求出这一部分的最大得分？可以先将所有的 y(i) 累加在 ignore 上，如果有一条边 node->child(k) 被选中，相当于在 ignore 的基础上加上 x(k) - y(k) + graph[node][child(k)]，求最大值就相当于寻找最大的 x(k) - y(k) + graph[node][child(k)]，可以建立一个列表维护所有的 x(i) - y(i) + graph[node][child(i)]，再遍历结束后取最大者加到 ignore 上；要注意，如果所有的值都是负数，不选择是最优的结果，因此可以在列表中预先添加一个 0，表示不选择任何的 node->child(i)。
            ignore += next[1];
            path.add(next[0] - next[1] + (long) graph.get(node).get(child));
        }
        long max = 0;
        for (long x : path)
            max = Math.max(max, x);
        ignore += max;
        return new long[] {choose, ignore};
    }

    public long maxScore(int[][] edges) {
        int n = edges.length;
        // 将数组还原成图
        for (int i = 0; i < n; i++)
            graph.add(new HashMap<Integer, Integer>());
        for (int i = 0; i < n; i++) {
            if (edges[i][0] == -1)
                continue;
            graph.get(edges[i][0]).put(i, edges[i][1]);
        }
        // 从根节点开始，一开始父节点是个不存在的节点，返回 traverse(0)[1] 即可
        return traverse(0)[1];
    }
}

python3 解法, 执行用时: 836 ms, 内存消耗: 214.2 MB, 提交时间: 2023-10-21 22:29:16 

class Solution:
    def maxScore(self, edges: List[List[int]]) -> int:
        n = len(edges)
        g = [[] for _ in range(n)]
        for i, [fa, w] in enumerate(edges):
            if i == 0: continue
            g[fa].append((i, w))
            
        @cache
        def dfs(u, state):
            # 叶子结点没有子节点 返回0
            if not g[u]:
                return 0
            ans = res = 0
            # 假如一条边都不选
            for v, w in g[u]:
                ans += dfs(v, False)
            # 当前点已经被选过了，所以儿子一个都不能选
            if state: return ans
            # 当前点没被选中，那只能选一个儿子，并且其他儿子都不选
            for v, w in g[u]:
                res = max(res, ans - dfs(v, False) + dfs(v, True) + w)
            return max(ans, res)
        return dfs(0, False)
        

    def maxScore2(self, edges: List[List[int]]) -> int:
        """在树中选择一些边使得选出的边不相连，最大化边权之和"""

        def dfs(cur: int, pre: int) -> Tuple[int, int]:
            """返回[选择连接父亲的边时子树最大价值, 不选择连接父亲的边时子树最大价值]

            如果选到父亲的边,所有儿子都不能选
            如果不选到父亲的边,所有儿子中选一个diff最大的
            """
            res1, res2 = 0, 0
            diff = [0]
            for next in adjMap[cur]:
                select, jump = dfs(next, cur)
                res1, res2 = res1 + jump, res2 + jump
                diff.append(select + adjMap[cur][next] - jump)

            res2 += max(diff)
            return res1, res2

        adjMap = defaultdict(lambda: defaultdict(lambda: -inf))
        for cur, (parent, weight) in enumerate(edges):
            if parent == -1:
                continue
            adjMap[parent][cur] = weight

        return max(0, dfs(0, -1)[1])  # 不连接虚拟根节点

上一题

© 2024 leetcode.cn