#CW38. Balance Tree(young)
Balance Tree(young)
题目描述
小 W 研究一棵带权树。为了让树的三个部分尽量均衡,他要删去恰好两条边,将原树分成三棵非空的树。
给定一棵有 个结点的无根树,第 个结点的权值为 。删去两条不同的边后,原树会分成三个连通块。一个连通块的权值定义为其中所有结点权值之和。
请最大化三个连通块权值的中位数。也就是说,将三个权值从小到大排列后,最大化排在第二位的数。
输入格式
第一行一个整数 。
第二行 个整数 。
接下来 行,每行两个整数 ,表示结点 与 之间有一条边。输入保证给出的是一棵树,结点编号为 至 。
输出格式
输出一个整数,表示答案。
样例 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
数据范围
对于所有数据:
- ;
- ;
- ,且输入图是一棵树。
| 数据类别 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| A | 10 | ||
| B | |||
| C | 5 | 树是一条链,且 | |
| D | 35 | ||
| E | 20 | ||
| F | 无附加限制 |