分数: 500 点
问题陈述
有一棵树 T 与 N 顶点。
顶点被标记为顶点 1,顶点 2, \ldots,顶点 N,并且边缘被标记为边缘 1,边缘 2, \ldots,边缘 (N-1).
边缘 i (1\leq i\leq N-1) 连接顶点 U_i 和 V_i.
每个顶点都有一个权重;最初,每个顶点的权重为 1.
你被给予 Q 查询按顺序处理。 每个查询属于以下两种类型之一:
1 x w:增加顶点的权重 x by w.2 y:如果边缘 y 被移除,该树 T 将被分成两个子树(连接的组件)。对于每个子树,令其权重为其顶点权重之和。输出两个子树的权重之差。
对于第二种类型的查询,可以证明删除 T 总是将其分成正好两个子树。
请注意,第二种类型的查询实际上不会删除边缘。
约束
- 2 \leq N \leq 3 \times 10^5
- 1 \leq U_i, V_i \leq N
- 1 \leq Q \leq 3 \times 10^5
- 1 \leq x \leq N
- 1 \leq w \leq 1000
- 1 \leq y \leq N-1
- 所有输入值均为整数。
- 给定的图是一棵树。
- 至少有一个第二类型的查询。
输入
输入由标准输入按以下格式给出:
N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询 \mathrm{query}_i (1\leq i\leq Q) 采用以下格式之一给出:
1 x w
2 y
输出
让 K 是第二类查询的数量。 输出 K 行;的 i- 第行 (1 \leq i \leq K)应包含以下问题的答案 i第二类型的第一个查询。
示例输入 1
6 1 2 1 3 2 4 4 5 4 6 5 2 1 1 1 3 2 1 1 4 10 2 5
示例输出 1
2 1 17
树的结构 T 和顶点编号如下图左侧所示。最初,每个顶点的权重为 1.
在第一个查询中,考虑删除边 1.
树分裂成包含顶点的子树 1 和包含顶点的子树 2。
有顶点的子树 1 有重量 2;有顶点的子树 2 有重量 4。输出差值, 2 (下图右)。

第二个查询增加了顶点的权重 1 by 3.
在第三个查询中,考虑删除边 1.
有顶点的子树 1 有重量 5;有顶点的子树 2 有重量 4。输出差值, 1 (下图左)。
第四个查询增加了顶点的权重 4 by 10.
在第 5 个查询中,考虑删除边 5.
树分裂成包含顶点的子树 4 和仅由顶点组成的子树 6.
有顶点的子树 4 有重量 18;有顶点的子树 6 有重量 1。输出差值, 17 (下图右)。

因此,按顺序输出第二类查询的答案: 2, 1,和 17,以换行符分隔。