Maximum Weighted Subset on a Tree with Subtree Majority Constraint

You are given a rooted tree \(G=(V,E)\) with \(n\) nodes, rooted at node \(1\). Each node \(i\) has an integer weight \(w_i\). For every node \(i\), let \(V_i\) denote the set of nodes in the subtree rooted at \(i\) (including \(i\) itself). You are to choose a subset \(V' \subseteq V\) such that for every node \(i\), the number of chosen nodes in its subtree satisfies

[ |V_i \cap V'| \le \left\lfloor \frac{|V_i|}{2} \right\rfloor, ]

The goal is to maximize the total weight of the chosen nodes, i.e., maximize

[ \sum_{i \in V'} w_i. ]

Output the maximum possible sum.

inputFormat

The first line contains an integer \(n\) denoting the number of nodes in the tree. The second line contains \(n\) space-separated integers \(w_1, w_2, \ldots, w_n\) representing the weights of the nodes. Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), denoting that there is an edge between nodes \(u\) and \(v\). It is guaranteed that the tree is connected and rooted at node \(1\).

outputFormat

Output a single integer representing the maximum sum of the weights of the selected nodes satisfying the constraint.

sample

1
5

0