You are given a weighted tree consisting of n nodes numbered from 0 to n - 1.
The tree is rooted at node 0 and represented with a 2D array edges of size n where edges[i] = [pari, weighti] indicates that node pari is the parent of node i, and the edge between them has a weight equal to weighti. Since the root does not have a parent, you have edges[0] = [-1, -1].
Choose some edges from the tree such that no two chosen edges are adjacent and the sum of the weights of the chosen edges is maximized.
Return themaximum sum of the chosen edges.
Note :
You are allowed to not choose any edges in the tree, the sum of weights in this case will be 0.
Two edges Edge1 and Edge2 in the tree are adjacent if they have a common node.
In other words, they are adjacent if Edge1 connects nodes a and b and Edge2 connects nodes b and c.
Input: edges =[[-1,-1],[0,5],[0,10],[2,6],[2,4]]Output: 11Explanation: The above diagram shows the edges that we have to choose colored in red.The total score is5+6=11.It can be shown that no better score can be obtained.
Example 2:
1
2
3
4
Input: edges =[[-1,-1],[0,5],[0,-6],[0,7]]Output: 7Explanation: We choose the edge with weight 7.Note that we cannot choose more than one edge because all edges are adjacent to each other.
We need to select a subset of edges in a tree such that no two selected edges are adjacent and the sum of their weights is maximized. This is a classic tree DP problem, similar to the “maximum weight independent set” but on edges instead of nodes.
For each node, we can decide for each child edge whether to include it or not. If we include an edge, we cannot include any edge adjacent to it (i.e., edges connected to its endpoints). We use DP to keep track of two states for each node: the maximum sum if the edge to its parent is not chosen, and the maximum sum if it is chosen.
classSolution {
publiclongmaximumScore(int[][] edges) {
int n = edges.length;
List<int[]>[] g =new ArrayList[n];
for (int i = 0; i < n; i++) g[i]=new ArrayList<>();
for (int i = 1; i < n; i++) {
int p = edges[i][0], w = edges[i][1];
g[p].add(newint[]{i, w});
}
long[]dfs(int u) {
long notChosen = 0, chosen = 0;
for (int[] e : g[u]) {
long[] res = dfs(e[0]);
notChosen += Math.max(res[0], res[1]);
chosen += res[0]+ e[1];
}
returnnewlong[]{notChosen, chosen};
}
return dfs(0)[0];
}
}
classSolution {
funmaximumScore(edges: Array<IntArray>): Long {
val n = edges.size
val g = Array(n) { mutableListOf<Pair<Int, Int>>() }
for (i in1 until n) {
val(p, w) = edges[i]
g[p].add(i to w)
}
fundfs(u: Int): Pair<Long, Long> {
var notChosen = 0L; var chosen = 0Lfor ((v, w) in g[u]) {
val(nc, c) = dfs(v)
notChosen += maxOf(nc, c)
chosen += nc + w
}
return notChosen to chosen
}
return dfs(0).first
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defmaximum_score(self, edges: list[list[int]]) -> int:
n = len(edges)
g = [[] for _ in range(n)]
for i in range(1, n):
p, w = edges[i]
g[p].append((i, w))
defdfs(u: int) -> tuple[int, int]:
not_chosen, chosen =0, 0for v, w in g[u]:
nc, c = dfs(v)
not_chosen += max(nc, c)
chosen += nc + w
return not_chosen, chosen
return dfs(0)[0]