Distance Tree (easy version) solution codeforces
This version of the problem differs from the next one only in the constraint on .
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.
You are given a weighted tree withvertices, each edge has a weight of . Denote as the distance between vertex and vertex .
Letbe the minimum possible value of if you can temporarily add an edge with weight between any two vertices and . Note that after this operation, the graph is no longer a tree.
For each integerfrom to , find .
The first line co ntains a single integer( ) — the number of test cases.
The first line of each test case contains a single integer( ).
Each of the nextlines contains two integers and ( ) indicating that there is an edge between vertices and . It is guaranteed that the given edges form a tree.
It is guaranteed that the sum ofover all test cases doesn’t exceed .
For each test case, printintegers in a single line, -th of which is equal to for all from to .
3 4 1 2 2 3 1 4 2 1 2 7 1 2 1 3 3 4 3 5 3 6 5 7
output Distance Tree (easy version) solution codeforces
1 2 2 2 1 1 2 2 3 3 3 3 3
- For , we can an edge between vertices and , then and , so .
- For , no matter which edge we add, , and , so .