Problem #4941 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 1024 MB

A tree is a connected undirected graph without cycles. A weighted tree has a weight assigned to each edge. The distance between two vertices is the minimum sum of weights on the path connecting them.

Cuber QQ has two weighted trees $T_{1}$ and $T_{2}$ , both two trees contain $n$ vertices. Denote $d (T, i, j)$ as the distance between vertex $i$ and vertex $j$ in tree $T$ .

Cuber QQ proposes a new distance, Two-Tree Distance (TTD), where $TTD (i, j) = d (T_{1}, i, j) + d (T_{2}, i, j)$ .

Now, for each vertex $i$ , Cuber QQ wants to find the nearest vertex $j$ , i.e., $j = arg {min}_{j^{‘} \neq i} TTD (i, j^{‘})$ and then output $TTD (i, j)$ .

输入格式

The first line contains a single integer $n$ ( $2 \leq n \leq 10^{5}$ ).

Each of the next $n - 1$ lines contains three integers $u, v$ and $w$ ( $1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^{9}$ ), indicating that there is an edge between vertices $u$ and $v$ with wright of $w$ in $T_{1}$ . It is guaranteed that the given edges form a tree.

Each of the next $n - 1$ lines contains three integers $u, v$ and $w$ ( $1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^{9}$ ), indicating that there is an edge between vertices $u$ and $v$ with wright of $w$ in $T_{2}$ . It is guaranteed that the given edges form a tree.

输出格式

The output contains $n$ lines, in $i$ -th line, a single integer indicates the minimized Two-Tree Distance of vertex $i$ .

样例

Input

Output

5 人解决，11 人已尝试。

6 份提交通过，共有 83 份提交。

8.3 EMB 奖励。

创建: 2 年，5 月前.

修改: 2 年，5 月前.

最后提交: 1 月，4 周前.

来源: N/A

4941. Tree

输入格式

输出格式

样例

服务

开源

关于我们