# 心灵支配树

- 参考时间限制：**2.0 秒**（[评测环境与性能](../../../docs/评测环境与性能.md)）。
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 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和3通过节点2相连，节点2的代价为5](assets/controlled-path.svg)

图 1：当受控制的战场节点为 $\{1,3\}$ 时，在节点 $1$ 、$2$ 或 $3$ 会合都只需消灭节点 $2$ 的单位，代价为 $5$ .

## 输入格式

第一行一个整数 $n$ .接下来 $n$ 行，第 $i$ 行给出 $v_i,e_i$ .随后 $n-1$ 行，每行两个整数 $a,b$ ，表示树的一条无向边。

## 输出格式

输出 $n$ 行，第 $u$ 行为启动节点 $u$ 后的最小代价。

## 样例 1

### 输入

```text
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
```

### 输出

```text
0
2
0
0
2
0
0
```

### 解释

启动节点 $2$ 时，受控制的战场节点为 $\{7,2,6\}$ ，连接它们还需经过节点 $1,5$ ，代价为 $2$ .启动根节点时所有单位都被控制，代价为零。

## 样例 2

### 输入

```text
4
3 2
5 4
7 1
11 3
1 2
2 3
3 4
```

### 输出

```text
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% | 无额外条件 |