|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||512 MB||66||20||11||27.500%|
Andi has N gears (numbered from 1 to N) on a board. Each gear has an arrow initially pointing upward. Some pair of gears may touch each other. If we construct a graph where each gear is a node, and we connect each pair of touching gears with an edge, then the structure of this graph is a tree. For example, the following is a possible gear configuration example with N = 4 gears and gear 2 touches all other gears.
Standard gear rotation rule applies: Suppose a gear u touches another gear v, and gear u is rotated α degrees clockwise, then gear v will be rotated α degrees counter-clockwise, and vice-versa.
Andi wants to perform three kinds of operations:
Let δu be the arrow’s degree (clockwise, modulo 360) of gear u after Q operations are done. Andi wants to know the sum of δu for all u. Furthermore, since rotating gears requires a lot of work, Andi also wants to know how much energy he needs for every Type 3 operation (rotating a gear). The amount of energy Andi needs to perform the Type 3 operation is defined as <number of rotating gears> × <rotation done in degrees>.
Input begins with a line containing an integer N (1 ≤ N ≤ 100000) representing the number of gears. The next N − 1 lines, each contains two integers: u v (1 ≤ u, v ≤ N; u ≠ v) representing that gear u and gear v touches each other. It is guaranteed that the structure of the connected gears forms a tree. The next line contains an integer Q (1 ≤ Q ≤ 100000) representing the number of operations. The next Q lines, each representing an operation to be done sequentially. Each operation is given in one of the following formats:
For each Type 3 operation in the same order as input, output in a line the amount of energy needed to rotate the gears. Finally, output in a line the sum of δu for all u.
4 1 2 2 3 2 4 8 3 2 160 1 2 3 1 10 3 3 10 3 4 10 2 2 1 1 3 3 15
640 10 10 10 45 805
The structure of the gears for this sample is illustrated by the figure in the problem description. The following table illustrates the state of each gear after each operation.
|Gear 1||Gear 2||Gear 3||Gear 4|
Therefore, the sum of δu for all u is 210 + 145 + 225 + 225 = 805.