All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Dr.Zero lives in Treeland. Tree land consists of a tree with N nodes connected by N-1 weighted undirected edges. The nodes of the tree are numbered from 1 to N. The tree is rooted at node 1.
Dr. Zero wanted to create a super amazing experiment. Before starting the experiment, he has laid out few important definitions needed.
- A subtree rooted at node x is defined recursively. It contains node x and the nodes in the subtrees of its children nodes.
- The strategic cost of a node in the subtree is defined as the distance to the farthest node from it in the whole subtree.
- The strategic cost of a subtree is defined by the minimum of strategic cost of all the nodes in the subtree.
In the experiment, he found strategic cost of subtree of each node in the tree. Sadly, he has misplaced the paper containing those results and now seeks your help.
The first line of input contains one integer T, the number of test cases.
For each test case: the first line contains N, the number of nodes.
In the next N-1 lines, each line contains 3 integers u,v,w which indicates an edge between node u and v with length w.
For each test case, output N lines, i-th of those should contain an integer corresponding to the strategic cost of subtree rooted at vertex i.
- 1 ≤ T ≤ 50
- 1 ≤ N ≤ 10^5
- 1 ≤ w ≤ 10^4
Subtask #1 (10 points)
- 1 ≤ N ≤ 100
- All edges are connected to node number 1
Subtask #2 (20 points)
- 1 ≤ N ≤ 100
Subtask #3 (30 points)
- 1 ≤ N ≤ 2000
Subtask #4 (40 points)
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 105
Input: 1 6 1 2 5 1 5 6 2 3 2 2 4 1 3 6 1 Output: 8 3 1 0 0 0
The cost of the tree rooted at vertex 1 is 8, because the vertex with the minimum strategic cost is 1 and the farthest vertex from it 6 with distance 8.
The cost of the tree rooted at vertex 2 is 3, here both vertices 2 and 3 have minimum strategic cost; the farthest vertex from 3 is 4 with distance 3 and the farthest vertex from 2 is 6 with distance 3 as well.
In the tree rooted at 3, both 3 and 6 have minimum strategic cost.
The rest of the trees are single-node trees because they're rooted at leaves.
|Tags||alex77, april16, jump-pointer, medium, tree|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions