406372: GYM102391 K Wind of Change

The original title of this problem is "Tree Product Metric Voronoi Diagram Query Without One Point".

You are given two weighted trees $$$T_1,\ T_2$$$ of size $$$N$$$, where each vertex are labeled with numbers $$$1 \ldots N$$$. Let $$$dist(T_1,\ i,\ j)$$$ be the total weight of the shortest path from node $$$i$$$ to $$$j$$$ in tree $$$T_1$$$, and define $$$dist(T_2,\ i,\ j)$$$ similarly.

Consider a point set of size $$$N$$$. Similar to Manhattan metric (in fact, this is a generalization of it), we can define the distance between two points $$$1 \le i,\ j \le N$$$: It is the sum of two distances, $$$dist(T_1,\ i,\ j) + dist(T_2,\ i,\ j)$$$. For each $$$1 \le i \le N$$$, please determine the "closest point" from the point $$$i$$$. Formally, for each $$$i$$$, you should find $$$min_{j \neq i}{dist(T_1,\ i,\ j) + dist(T_2,\ i,\ j)}$$$.

In the first line, a single integer $$$N$$$ denoting the number of vertices in both trees is given. ($$$2 \le N \le 250\,000$$$)

In the next $$$N-1$$$ lines, description of the first tree is given. Each of the $$$N-1$$$ lines contains three integers $$$S_i, E_i, W_i$$$, which indicates there is an edge connecting two vertices $$$S_i, E_i$$$ with weight $$$W_i$$$ ($$$1 \le S_i, E_i \le N, 1 \le W_i \le 10^9$$$)

In the next $$$N-1$$$ lines, description of the second tree is given in the same format.

Print $$$N$$$ lines containing a single integer. In the $$$i$$$-th line, you should print a single integer denoting the answer for the point $$$i$$$.

5
1 2 10
2 4 20
3 4 30
4 5 50
1 2 15
1 3 25
1 4 35
1 5 25

25
25
85
65
105

9
5 7 6577
4 5 8869
5 9 9088
2 1 124
6 2 410
2 8 8154
4 8 4810
3 4 4268
3 9 763
6 2 8959
7 4 7984
3 8 504
8 6 9085
5 2 4861
1 9 8539
1 7 7834

18084
9369
9582
23430
26694
9369
23430
9582
22988