LeetCode 2378: Choose Edges to Maximize Score in a Tree Solution

Master LeetCode problem 2378 (Choose Edges to Maximize Score in a Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2378. Choose Edges to Maximize Score in a Tree

Medium

Dynamic Programming Tree Depth-First Search

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2378 (Choose Edges to Maximize Score in a Tree)?

This page provides optimized solutions for LeetCode problem 2378 (Choose Edges to Maximize Score in a Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2378 (Choose Edges to Maximize Score in a Tree)?

The time complexity for LeetCode 2378 (Choose Edges to Maximize Score in a Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2378 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2378 in Java, C++, or Python.

Back to LeetCode Solutions