#CW38. Balance Tree(young)

Balance Tree(young)

题目描述

小 W 研究一棵带权树。为了让树的三个部分尽量均衡,他要删去恰好两条边,将原树分成三棵非空的树。

给定一棵有 nn 个结点的无根树,第 ii 个结点的权值为 wiw_i。删去两条不同的边后,原树会分成三个连通块。一个连通块的权值定义为其中所有结点权值之和。

请最大化三个连通块权值的中位数。也就是说,将三个权值从小到大排列后,最大化排在第二位的数。

输入格式

第一行一个整数 nn。

第二行 nn 个整数 w1,w2,…,wnw_1,w_2,\dots,w_n。

接下来 n−1n-1 行,每行两个整数 u,vu,v,表示结点 uu 与 vv 之间有一条边。输入保证给出的是一棵树,结点编号为 11 至 nn。

输出格式

输出一个整数,表示答案。

样例 1 输入

5
2 2 3 3 1
1 2
2 3
2 4
1 5

样例 1 输出

3

样例 2 输入

5
1 3 -2 3 1
1 2
2 3
3 4
4 5

样例 2 输出

4

数据范围

对于所有数据:

  • 3≤n≤5×1053 \le n \le 5 \times 10^5;
  • ∣wi∣≤109|w_i| \le 10^9;
  • 1≤u,v≤n1 \le u,v \le n,且输入图是一棵树。
数据类别 分值 测试点 附加条件
A 10 1∼21\sim 2 n≤10n \le 10
B 3∼43\sim 4 n≤5000n \le 5000
C 5 55 树是一条链,且 n≤105n \le 10^5
D 35 6∼126\sim 12 n≤105n \le 10^5
E 20 13∼1613\sim 16 n≤3×105n \le 3\times 10^5
F 17∼2017\sim 20 无附加限制