Problem 3589. -- 动态树 -- 衡阳八中OJ离线版-2014-11-04

　　小明在楼下种了一棵动态树, 该树每天会在某些节点上长出一些果子. 这棵树的根节点为1, 它有n个节点, n-1条边.

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

　　事件0:
　　这棵树长出了一些果子, 即某个子树中的每个节点都会长出K个果子.

　　事件1:
　　小明希望你求出几条树枝上的果子数. 一条树枝其实就是一个从某个节点到根的路径的一段. 每次小明会选定一些树枝, 让你求出在这些树枝上的节点的果子数的和. 注意, 树枝之间可能会重合, 这时重合的部分的节点的果子只要算一次.

　　初始时, 每个节点上都没有果子.

Input

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

Output

　　对于每个事件1, 输出询问的果子数.

Sample Input

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

Sample Output

HINT

1 <= n <= 200,000, 1 <= nQ <= 200,000, K = 5.

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

3589: 动态树