No Two Neighbours Chosen

Difficulty: 1700 6000 ms 128 MB

dp trees

Each node of a tree has a weight. Choose a set of nodes with NO two adjacent, maximizing the total weight.

Input: the first line has N; the second line has the N weights; the next N−1 lines have the edges.

Output: the maximum weight of an independent set.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ w_i ≤ 1000

Sample Tests

4
3 1 4 1
1 2
1 3
3 4

5

1
9

9

Read the Editorial