动态树

题目描述

别忘了这是一棵动态树，每时每刻都是动态的。小明要求你在这棵树上维护两种事件。

1. 0 u delta，这棵树长出了一些果子, 即$u$的子树中的每个节点都会长出$delta$个果子.
2. 1 k u1 v1 ... uk vk，小明希望你求出几条树枝上的果子数. 一条树枝其实就是一个从某个节点到根的路径的一段. 每次小明会选定一些树枝, 让你求出在这些树枝上的节点的果子数的和。注意, 树枝之间可能会重合, 这时重合的部分的节点的果子只要算一次。

输入格式

第一行一个整数$n(1 \leq n\leq 2\times 10^5)$，即节点数。

接下来$n - 1$行, 每行两个数字$u, v$，表示果子$u$和果子$v$之间有一条直接的边。 节点从$1$开始编号。

在接下来一个整数$q (1\leq q\leq 2\times 10^5)$，表示事件。

最后$q$行，每行开头要么是$0$，要么是$1$。

如果是$0$，表示这个事件是事件$0$。这行接下来的 2 个整数$u, delta (1\leq delta\leq 10 ^ 9)$表示以$u$为根的子树中的每个节点长出了$delta$个果子。

如果是$1$，表示这个事件是事件$1$。这行接下来一个整数$k (1\leq k \leq 5)$，表示这次询问涉及$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