P7130 「RdOI R1」平衡常数(balance)

给定一棵以 $1$ 为根的点带权有根树 $G=(V,E)$，第 $i$ 个节点的权值记为 $w_i$，以 $i$ 为根的子树的点集记为 $V_i$，求一个点集 $V'\subseteq V$，满足以下条件： - $\forall i$，都有 $|V_i \cap V'| \le \lfloor \frac{|V_i|}{2} \rfloor$ - 最大化 $\sum _{i \in V'} w_i$ 输出 $\sum _{i\in V'} w_i$ 即可，也就是选取的点的权值和。

第一行为一个正整数 $n$。 第二行为 $n$ 个正整数 $w_i$。 接下来 $n-1$ 行每行为两个整数 $u,v$，表示第 $i$ 条边的两个端点。

输出只有一行，为你所求得的最大总和。

【数据范围】 | 测试点编号 | $n\leq$ | $w_i\leq$ | 特殊性质 | | - | - | - | - | | $1\sim2$ | $10$ | $10^3$ | | | $3\sim 5$ | $2 \times 10^3$ | $10^3$ | | | $6\sim12$ | $10^5$ | $10^3$ | | | $13\sim16$ | $5 \times 10^5$ | $10^9$ | $v=u+1$ | | $17\sim25$ | $5 \times 10^5$ | $10^9$ | | 对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$0 < w_i \leq 10^9$，$1 \leq u,v \leq n$。 --- 【说明/提示】 - Idea From : LCuter --- 【文件读入读出】**（模拟，提交代码时不需使用）** - 文件名：`balance.cpp` - 读入文件名：`balance.in` - 读出文件名：`balance.out`