← 返回题目列表

AtCoder · abc406_f

I. 比较树权重

中文机器翻译题面 查看原题

分数: 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,以换行符分隔。