题目描述

别忘了这是一棵动态树，每时每刻都是动态的。

小明要求你在这棵树上维护两种事件：

事件 $0$：
这棵树长出了一些果子，即某个子树中的每个节点都会长出 $k$ 个果子。

事件 $1$：
小明希望你求出几条树枝上的果子数。一条树枝其实就是一个从某个节点到根的路径的一段。

每次小明会选定一些树枝，让你求出在这些树枝上的节点的果子数的和。注意，树枝之间可能会重合，这时重合的部分的节点的果子只要算一次。

输入格式

第一行一个整数 $n$，即节点数。
接下来 $n-1$ 行，每行两个数字 $u,v$。表示果子 $u$ 和果子 $v$ 之间有一条直接的边。节点从 $1$ 开始编号。
再接下来一个整数 $nQ$，表示事件。
最后 $nQ$ 行，每行开头要么是 $0$，要么是 $1$。
如果是 $0$，表示这个事件是事件 $0$。这行接下来的 $2$ 个整数 $u,delta$ 表示以 $u$ 为根的子树中的每个节点长出了 $delta$ 个果子。
如果是 $1$，表示这个事件是事件 $1$。这行接下来一个整数 $k$，表示这次询问涉及 $k$ 个树枝。接下来 $k$ 对整数 $u_k,v_k$，每个树枝从节点 $u_k$ 到节点 $v_k$ 。由于果子数可能非常多，请输出这个数模 $2^{31}$ 的结果。

输出格式

对于每个事件 $1$，输出询问的果子数。

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

13

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le nQ\le 2\times 10^5$，$k=5$。

生成每个树枝的过程是这样的：先在树中随机找一个节点，然后在这个节点到根的路径上随机选一个节点，这两个节点就作为树枝的两端。

题目来源

By 佚名提供