시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 (추가 시간 없음) | 1024 MB | 397 | 49 | 32 | 19.162% |
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, each 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
University > KAIST > 2019 KAIST 9th ICPC Mock Competition K번
Contest > Open Cup > 2019/2020 Season > Stage 5: Grand Prix of Korea K번