心灵支配树¶
- 参考时间限制：2.0 秒（评测环境与性能）。
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB
背景故事¶
心灵军团用一棵支配树控制战场单位。启动一个节点后，它及其全部后代的控制效果同时生效。战场与支配树具有相同的树形道路结构；被控制的单位需要会合，途中未被控制的敌军必须先被消灭。请评估每个启动节点所需的最小代价。
形式化问题描述¶
给定一棵 \(n\) 个节点的树，节点编号为 \(1\) 到 \(n\) ，以节点 \(1\) 为根。同一棵树同时表示支配关系和战场道路。
战场节点 \(i\) 有一支战斗力为 \(v_i\) 的单位。支配节点 \(i\) 控制战场节点 \(e_i\) 的单位，且 \(e\) 是 \(1\) 到 \(n\) 的一个排列。
对于每个支配节点 \(u\) ，令 \(S_u\) 为 \(u\) 的子树中所有节点所控制的战场节点集合。选择任意战场节点作为会合点，让 \(S_u\) 中的单位沿树上的道路移动到该点。需要经过的未受控制单位必须被消灭，每支仅计一次代价；受控制单位不产生代价，会合点上的未受控制单位也需计入。
求每个 \(u\) 的最小总代价。各个 \(u\) 的方案独立计算。
图 1：当受控制的战场节点为 \(\{1,3\}\) 时，在节点 \(1\) 、\(2\) 或 \(3\) 会合都只需消灭节点 \(2\) 的单位，代价为 \(5\) .
输入格式¶
第一行一个整数 \(n\) .接下来 \(n\) 行，第 \(i\) 行给出 \(v_i,e_i\) .随后 \(n-1\) 行，每行两个整数 \(a,b\) ，表示树的一条无向边。
输出格式¶
输出 \(n\) 行，第 \(u\) 行为启动节点 \(u\) 后的最小代价。
样例 1¶
输入¶
7
1 1
1 7
1 2
1 6
1 5
1 4
1 3
1 2
2 3
2 4
1 5
5 6
5 7
输出¶
0
2
0
0
2
0
0
解释¶
启动节点 \(2\) 时，受控制的战场节点为 \(\{7,2,6\}\) ，连接它们还需经过节点 \(1,5\) ，代价为 \(2\) .启动根节点时所有单位都被控制，代价为零。
样例 2¶
输入¶
4
3 2
5 4
7 1
11 3
1 2
2 3
3 4
输出¶
0
5
5
0
解释¶
启动节点 \(3\) 后控制战场节点 \(1,3\) ，必须经过节点 \(2\) ，代价为 \(v_2=5\) .启动节点 \(2\) 后再多控制节点 \(4\) ，仍只需支付节点 \(2\) 的代价。
数据范围与保证¶
- \(1\le n\le100000\) ，\(1\le v_i\le5000\) .
- \(e\) 是 \(1\) 到 \(n\) 的排列；输入边构成一棵树。
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |