5 人解决，10 人已尝试。
6 份提交通过，共有 82 份提交。
8.2 EMB 奖励。
单点时限: 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 $\text{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=\text{arg} \text{min}_{j^{‘}\neq i} \text{TTD}(i,j^{‘})$ and then output $\text{TTD}(i,j)$.
The first line contains a single integer $n$ ($2\le n\le 10^5$).
Each of the next $n-1$ lines contains three integers $u,v$ and $w$ ($1\le u,v\le n,u\neq v,1\le w\le 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\le u,v\le n,u\neq v,1\le w\le 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$.
5 1 2 1 2 4 2 3 4 3 4 5 4 1 2 2 1 3 3 1 4 4 2 5 5
3 3 9 7 11
5 人解决，10 人已尝试。
6 份提交通过，共有 82 份提交。
8.2 EMB 奖励。
创建: 2 年前.
修改: 2 年前.
最后提交: 1 年，8 月前.
来源: N/A