P12693 BZOJ3589 动态树

别忘了这是一棵动态树，每时每刻都是动态的。 小明要求你在这棵树上维护两种事件： - 事件 0：这棵树长出了一些果子，即某个子树中的每个节点都会长出 $k$ 个果子。 - 事件 1：小明希望你求出几条树枝上的果子数。一条树枝其实就是一个从某个节点到根的路径的一段。 每次小明会选定一些树枝，让你求出在这些树枝上的节点的果子数的和。注意，树枝之间可能会重合，这时重合的部分的节点的果子只要算一次。

第一行一个整数 $n$，即节点数。 接下来 $n - 1$ 行，每行两个数字 $u, v$。表示果子 $u$ 和果子 $v$ 之间有一条直接的边。节点从 $1$ 开始编号。 再接下来一个整数 $Q$，表示事件。 最后 $Q$ 行，每行开头要么是 $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$，输出询问的果子数。

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq Q \leq 2 \times 10^5$，$k = 5$。 生成每个树枝的过程是这样的：先在树中随机找一个节点，然后在这个节点到根的路径上随机选一个节点，这两个节点就作为树枝的两端。