[Answer] Hemose on the Tree solution codeforces
After the last regional contest, Hemose and his teammates finally qualified to the ICPC World Finals, so for this great achievement and his love of trees, he gave you this problem as the name of his team “Hemose 3al shagra” (Hemose on the tree).
You are given a tree ofvertices where is a power of . You have to give each node and edge an integer value in the range (inclusive), where all the values are distinct.
After giving each node and edge a value, you should select some root for the tree such that the maximum cost of any simple path starting from the root and ending at any other node or edge is minimized.
The cost of the path between two nodes bitwise XOR of all the node’s and edge’s values between them, including the endpoints (note that in a tree there is only one simple path between two nodes or between a node and an edge).and or any node and edge is defined as the
The first line contains a single integer( ) — the number of test cases. Then test cases follow.
The first line of each test case contains a single integer( ), where (the number of vertices in the tree) is equal to .
Each of the nextlines contains two integers and ( ) meaning that there is an edge between the vertices and in the tree.
It is guaranteed that the given graph is a tree.
It is guaranteed that the sum ofover all test cases doesn’t exceed .
For each test case on the first line print the chosen root.
On the second line, printintegers separated by spaces, where the -th integer represents the chosen value for the -th node.
On the third line, printintegers separated by spaces, where the -th integer represents the chosen value for the -th edge. The edges are numerated in the order of their appearance in the input data.
If there are multiple solutions, you may output any.
2 2 1 2 2 3 3 4 3 1 2 2 3 3 4 1 5 1 6 5 7 5 8
3 5 1 3 6 4 2 7 5 1 2 8 11 4 13 9 15 6 14 3 7 10 5 12
The tree in the first test case with the weights of all nodes and edges is shown in the picture.
The maximum cost of all these paths is. We can show that it is impossible to assign the values and choose the root differently to achieve a smaller maximum cost of all paths.
The tree in the second test case: