题目描述

给定一棵以 $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$ 条边的两个端点。

输出格式

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

3
1 2 3
1 2
1 3

1

提示

【数据范围】

对于 $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