Internet Problem Solving Contest

IPSC 2009

Problem L – Let there be rainbows!

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.

Each day, he picked two cities si and ti, and a color ci. Painters with an ample supply of the color ci were sent to the city si, and then they travelled to ti. On their way, whenever they encountered a road that did not have the color ci, they painted it to this color.

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.

Input specification

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.

Output specification

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.)



0 4
7 5
5 6
3 5
1 4
4 2
4 3
0 7 red
2 6 orange
4 3 green
1 7 green

0 1
1 2
2 3
2 4
2 5
0 6
6 7
7 8
7 9
7 10
11 6
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.