LeetCode 2378: Choose Edges to Maximize Score in a Tree
Problem Description
Explanation
Given a tree with n nodes and edge weights, we need to choose a subset of edges to maximize the score. The score of an edge is the product of the number of nodes in its two subtrees. We want to find the maximum possible sum of scores of the selected edges.
To solve this problem, we can use dynamic programming. We can perform a depth-first search (DFS) on the tree to calculate the subtree sizes and scores for each node. Then, we can use dynamic programming to calculate the maximum score for each node considering whether to include the current edge or not.
Solutions
class Solution {
int[] size, score;
List<List<Integer>> graph;
public int maxWeight(int[] parent, int[] wt) {
int n = parent.length + 1;
size = new int[n];
score = new int[n];
graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < parent.length; i++) {
graph.get(parent[i]).add(i + 1);
graph.get(i + 1).add(parent[i]);
}
dfs(0, wt);
return dp(0, -1);
}
private void dfs(int node, int[] wt) {
size[node] = 1;
score[node] = wt[node];
for (int child : graph.get(node)) {
if (size[child] == 0) {
dfs(child, wt);
size[node] += size[child];
score[node] += score[child];
}
}
}
private int dp(int node, int parent) {
int res = 0;
for (int child : graph.get(node)) {
if (child != parent) {
res = Math.max(res, dp(child, node));
res = Math.max(res, size[child] * (size[0] - size[child]));
}
}
return res;
}
}Loading editor...