#P13290. 树上的操作查询

    ID: 12473 传统题 文件IO:tree 6000ms 1024MiB 尝试: 60 已通过: 8 难度: 8 上传者: 标签>CF2500提高+/省选-交换求和顺序树链剖分子树转区间LCA懒标记线段树补集转化

树上的操作查询

树上的操作查询

给定一棵包含 NN 个顶点的树。顶点编号为 1 到 NN。
每个顶点上有一个变量 AiA_i,初始时 Ai=0 (1≤i≤N)A_i = 0\ (1 \le i \le N)。

你需要处理 QQ 次查询。每个查询有以下三种类型之一:


操作类型 1:1 u v

以顶点 uu 为根,将树重新定根。
考虑以顶点 vv 为根的子树,将该子树中所有顶点 ii 的 AiA_i 均加一。


操作类型 2:2 u v

在树中找到从顶点 uu 到顶点 vv 的唯一简单路径。
对于路径上的每个顶点 ii,令 AiA_i 加一。


操作类型 3:3 v

计算并输出:

∑i=1Ndist(v,i)×Ai\sum_{i=1}^{N} dist(v, i) \times A_i

其中 dist(x,y)dist(x, y) 表示顶点 xx 到顶点 yy 之间的边数。


输入格式

第一行输入一个整数 NN,表示顶点数。(1≤N≤2×105)(1 \le N \le 2 \times 10^5)

接下来 N−1N - 1 行,每行两个整数 u,vu, v,表示一条无向边。
保证输入构成一棵树。

然后输入一个整数 QQ,表示查询的数量。(1≤Q≤2×105)(1 \le Q \le 2 \times 10^5)

接下来 QQ 行,每行描述一个查询,格式如上所述。
保证至少存在一个类型为 3 的查询。


输出格式

对于每个类型为 3 的查询,输出一行一个整数表示答案。


示例

输入

5
4 2
2 5
1 5
1 3
5
2 2 4
3 4
2 1 5
2 5 5
3 2

输出

1
5

部分分

档次 分值 限制条件
第一档 10 分 N,Q≤10N, Q \le 10
第二档 15 分 N,Q≤1000N, Q \le 1000
第三档 25 分 仅包含类型 2、3 查询
第四档 仅包含类型 1、3 查询
第五档 无额外限制 (N,Q≤2×105)(N, Q \le 2 \times 10^5)

数据