NC207610. Letthereberainbows!
描述
Once upon a time there was the kingdom of Absurdistan. There were N cities in the kingdom.
As it is often the case, some pairs of cities were connected by roads. The Great Vizier of Absurdistan was a terrible scrooge, hence the road network was a tree. (I.e., for any pair of cities there was exactly one way how to get from one to the other, while travelling by roads.)
The roads were made of concrete blocks and they all had a dull grey color.
One day, the Great Vizier came to the conclusion that travelling along dull grey roads makes people unhappy. As he does not want to risk a revolution, he decided to paint the roads using happy colors – the 7 colors of the rainbow.
Problem specification
You are given the number of cities N, the description of the road network, and the sequence of Great Vizier’s orders.
For each order, compute the number of roads the painters had to repaint.
输入描述
The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
Each test case starts with line containing a positive integer N (N ≤ 1000000). For convenience, the cities in Absurdistan are numbered 0 to N - 1.
N - 1 lines follow. Each of these lines contains two numbers ai bi (0 ≤ ai,bi < N) – the endpoints of one road.
The next line contains a single integer Q (Q ≤ 200000) specifying the number of orders.
Q lines follow, each describing one order. Each description consists of two integers si ti (0 ≤ si,ti < N) and a string ci (ci is one of red, orange, yellow, green, blue, indigo, and violet).
In the easy input, you may also assume that for each test case except for one we have NQ ≤ 108. In the remaining test case the road network is a simple line.
输出描述
For each test case output seven lines. Each of these lines should contain a color name (in the order given above) and a number. The number shall be the total number of times some road was painted using the corresponding color.
You may output empty lines between the test cases. (The amount of whitespace in your output does not matter anyway; we do this for readability in the example below.)
示例1
输入:
2 8 0 4 7 5 5 6 3 5 1 4 4 2 4 3 4 0 7 red 2 6 orange 4 3 green 1 7 green 12 0 1 1 2 2 3 2 4 2 5 0 6 6 7 7 8 7 9 7 10 11 6 3 3 8 blue 6 1 violet 5 11 blue
输出:
red 4 orange 4 yellow 0 green 4 blue 0 indigo 0 violet 0 red 0 orange 0 yellow 0 green 0 blue 10 indigo 0 violet 2
说明:
We will explain the second test case in detail:
When executing the query “3 8 blue”, we paint six roads blue: 3-2, 2-1, 1-0, 0-6, 6-7, and 7-8.
When executing the query “6 1 violet”, we paint two roads violet: 6-0 and 0-1. (Both of these roads were previously blue.)
Finally, when executing the query “5 11 blue”, we paint four roads blue: 5-2, 1-0, 0-6, and 6-11. Note that the road 2-1 was still blue, hence we did not paint it now.
Thus we painted a road blue 6+4=10 times, and we painted a road violet 2 times.