P15952 [ICPC 2018 Jakarta R] Rotating Gears

安迪在一块板子上有 $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$ 之和。

**样例输入/输出解释** 本样例的齿轮结构如题目描述中的图示所示。下表展示了每次操作后每个齿轮的状态。 | 操作后 | $\delta_u$ | | | | |:---------------:|:-------------------------------:|:-----------:|:-----------:|:-----------:| | | 齿轮 1 | 齿轮 2 | 齿轮 3 | 齿轮 4 | | 初始 | $0$ | $0$ | $0$ | $0$ | | 1 | **$200$** | **$160$** | **$200$** | **$200$** | | 2 | $200$ | 已移除 | $200$ | $200$ | | 3 | **$210$** | 已移除 | $200$ | $200$ | | 4 | $210$ | 已移除 | **$210$** | $200$ | | 5 | $210$ | 已移除 | $210$ | **$210$** | | 6 | $210$ | $160$ | $210$ | $210$ | | 7 | 已移除 | $160$ | $210$ | $210$ | | 8 | 已移除 | **$145$** | **$225$** | **$225$** | 因此，所有 $u$ 的 $\delta_u$ 之和为 $210 + 145 + 225 + 225 = 805$。 翻译由 DeepSeek V3.2 完成