1229 . Shadow Hunters
Description
In the mystic kingdom of Zxcvbnm, there exists three groups of opposing force:
the Shadows, some of the most fearsome creeps that spawn from hell;
the Hunters, who are exorcists that hunt down the Shadows;
and the Neutral, which are those human that belong to neither side, struggling for their own purpose.
Before cutting into the story, we shall introduce the formation of kingdom Zxcvbnm.
Kingdom Zxcvbnm is formed by N cities numbered from 0 to N-1, with city 0 being the capital.
There are exactly N-1 roads connecting the N cities, thus forming a tree rooted at the capital (city 0).
From time to time, the three forces(Shadows, Hunters, and Neutral Human) would begin an expedition that cover some part of the kingdom Zxcvbnm, and they would raid whatever is oppose to them. To be clear, they choose a set of specific roads of the country according to certain rule(given later) and traverse every chosen road, destroying their enemies along the roads.
However the expedition route they choose are different by rule below:
The Shadows, living at the border of the country, always begin their expedition at some leaf city X, and they march toward the capital city until they reach city Y, where Y is a predecessor of X.
The Hunters, being determined to hunt down their enemy, choose a specific city X to start with, and march every road that is in the subtree rooted at X.
The Neutral Human on the other hand, always begin their expedition from the captial and marched along the only path from the capital to a specific city X.
Doraemon is a curious boy. He always wonder how many times a road is chosen (by any one of the three forces).
So given (in time order) the history of the expeditions of the three forces, answer Doraemon's question: how many time is the road (U,V) chosen as a road of expedition? Here the traversal of three forces are summed together to obtain the total number of times a road is used, and in each single expedition (of whichever force) a road is traversed once if it is chosen.
Note that Doraemon is so curious that he may ask question at certain different times, that is, in between the list of expedition histories. For such question, one should answer Doraemon according to the "current status", that is, according to ONLY those expeditions that are given already at that point.
Input Format
The first line of input consists of an integer T: the number of testcases.
In the beginning of each testcase there is a single number N: the number of cities in Zxcvbnm. (numbered from 0 to N-1)
The next N-1 lines each contain two integers (ui,vi) denoting the N-1 edges of kingdom Zxcvbnm.
After that there is a line containing a number Q: the number of expeditions/queries.
In the following Q lines, each line is in one of the four formats:
s X Y - The Shadows start an expidition that begin at leaf X and ends at node Y, where Y is a predecessor of X.
h X - The Hunters start an expedition that traveres every roads in the subtree rooted at X.
n X - Neutral human begin an expedition that marches from the capital to city X.
q U V - A question asked by doraemon. One should output how many time the road (U,V) is traversed. (U,V) is garunteed to be an valid edge.
Constraints:
1 <= T <= 50
1 <= N <= 100000
0 <= Q <= 100000
Output Format
For each of Doraemon's queries, output a single line containing a single number:
The number of time the road is traversed.
Sample Input 1
1 14 0 1 1 10 1 11 11 12 11 13 0 2 2 3 2 4 2 9 4 5 4 6 6 7 6 8 13 h 4 q 2 4 q 4 5 q 8 6 n 6 q 6 4 q 6 7 q 0 2 s 7 2 q 4 6 q 2 4 q 6 7 q 2 3
Sample Output 1
0 1 1 2 1 1 3 2 2 0
Hints
Problem Source
Migrated from old NTUJ.
Kelvin
Subtasks
| No. | Testdata Range | Score |
|---|