BackhardTrees

Optimal Subtree Sum Solution

Problem Statement

Given a tree with nodes having unique identifiers and non-negative integer weights, find the maximum sum of weights that can be obtained by removing a subset of nodes such that the remaining nodes form a connected subtree.

Example 1
Input
{"tree":{"nodes":[{"id":1,"weight":5},{"id":2,"weight":3},{"id":3,"weight":2},{"id":4,"weight":7}],"edges":[[1,2],[1,3],[2,4]]}}
Output
15

Explanation: Remove node 3 to get the maximum sum of 5 + 3 + 7 = 15

Example 2
Input
{"tree":{"nodes":[{"id":1,"weight":10},{"id":2,"weight":8},{"id":3,"weight":4},{"id":4,"weight":6}],"edges":[[1,2],[1,3],[2,4]]}}
Output
18

Explanation: Keep all nodes to get the maximum sum of 10 + 8 + 4 + 6 = 28, however the problem statement asks for the maximum sum after removing a subset of nodes, in this case removing no nodes gives the maximum sum of 28, the given output of 18 is incorrect.

Constraints

  • 1 <= number of nodes <= 100
  • Each node has a unique identifier
  • Weights are non-negative integers between 0 and 10^6

More Trees Problems

Count Single-Child NodeseasyAdaptive Path WeighteasyAdaptive Interval PartitioneasyAdaptive Subsequence Sumeasy
View all problems →
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free