Solution

Method 1 – Tree DP (Maximum Weight Independent Set on Edges)

Intuition

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.

Reasoning

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.

Approach

Build the tree as an adjacency list from the edges array.
For each node, define a DP function that returns two values:
- not_chosen: the maximum sum if the edge to its parent is not chosen.
- chosen: the maximum sum if the edge to its parent is chosen (cannot choose any child edge).
For each child, recursively compute its DP values.
- If the edge to the child is chosen, add its weight and the not_chosen value from the child.
- If not chosen, take the maximum of chosen and not_chosen from the child.

Related Tags