题目描述

安迪在一块板子上有 $N$ 个齿轮（编号为 $1$ 到 $N$）。每个齿轮初始时箭头指向上方。某些齿轮之间可能相互接触。如果我们构造一张图，其中每个齿轮是一个节点，每对相互接触的齿轮之间连一条边，那么这张图的结构是一棵树。例如，下图展示了一个可能的齿轮配置，其中 $N = 4$ 个齿轮，齿轮 $2$ 与所有其他齿轮接触。

:::align{center} :::

标准的齿轮旋转规则适用：假设齿轮 $u$ 与齿轮 $v$ 接触，且齿轮 $u$ 顺时针旋转 $\alpha$ 度，那么齿轮 $v$ 将逆时针旋转 $\alpha$ 度，反之亦然。

安迪想要执行三种类型的操作：

1. 将齿轮从板子上的位置取出。
2. 将齿轮放回其原始位置。执行此操作时，安迪以与取出时相同的角度方向放置齿轮，即箭头指向取出时的相同角度。假设总是可以做到这一点，即不需要考虑齿轮的机械结构。
3. 将齿轮顺时针旋转 $\alpha$ 度。

设 $\delta_u$ 为 $Q$ 次操作完成后齿轮 $u$ 箭头的角度（顺时针方向，模 $360$）。安迪想知道所有 $u$ 的 $\delta_u$ 之和。此外，由于旋转齿轮需要很多体力，安迪还想知道每次类型 3 操作（旋转齿轮）所需的能量。执行类型 3 操作所需的能量定义为 $\langle \text{旋转齿轮数量} \rangle \times \langle \text{旋转度数} \rangle$。

输入格式

输入的第一行包含一个整数 $N$（$1 \leq N \leq 100000$），表示齿轮的数量。接下来的 $N-1$ 行，每行包含两个整数 $u\ v$（$1 \leq u, v \leq N; u \neq v$），表示齿轮 $u$ 和齿轮 $v$ 相互接触。保证这些齿轮形成的图是一棵树。下一行包含一个整数 $Q$（$1 \leq Q \leq 100000$），表示操作的数量。接下来的 $Q$ 行，每行表示一个按顺序执行的操作。每个操作采用以下格式之一：

• 两个整数：$1\ x$（$1 \leq x \leq N$）。表示该操作将齿轮 $x$ 从板子上取出。保证齿轮 $x$ 当前在板子上。
• 两个整数：$2\ x$（$1 \leq x \leq N$）。表示该操作将齿轮 $x$ 放回其原始位置。保证齿轮 $x$ 当前不在板子上。
• 三个整数：$3\ x\ \alpha$（$1 \leq x \leq N; 0 \leq \alpha \leq 359$）。表示该操作将齿轮 $x$ 顺时针旋转 $\alpha$ 度。保证齿轮 $x$ 当前在板子上。

输出格式

对于每个类型 3 操作，按输入顺序输出一行，表示旋转齿轮所需的能量。最后，输出一行，表示所有 $u$ 的 $\delta_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

提示

样例输入/输出解释

本样例的齿轮结构如题目描述中的图示所示。下表展示了每次操作后每个齿轮的状态。

因此，所有 $u$ 的 $\delta_u$ 之和为 $210 + 145 + 225 + 225 = 805$。

翻译由 DeepSeek V3.2 完成