7589: BZOJ3589：动态树
Memory Limit：1024 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
别忘了这是一棵动态树, 每时每刻都是动态的. 小明要求你在这棵树上维护两种事件
事件0:
这棵树长出了一些果子, 即某个子树中的每个节点都会长出K个果子.
事件1:
小明希望你求出几条树枝上的果子数. 一条树枝其实就是一个从某个节点到根的路径的一段. 每次小明会选定一些树枝, 让你求出在这些树枝上的节点的果子数的和. 注意, 树枝之间可能会重合, 这时重合的部分的节点的果子只要算一次.
输入格式
第一行一个整数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的结果.
输出格式
对于每个事件1, 输出询问的果子数.
样例输入
5 1 2 2 3 2 4 1 5 3 0 1 1 0 2 3 1 2 3 1 1 4
样例输出
13
提示
1 <= n <= 200,000, 1 <= nQ <= 200,000, K = 5.
生成每个树枝的过程是这样的:先在树中随机找一个节点, 然后在这个节点到根的路径上随机选一个节点, 这两个节点就作为树枝的两端.
题目来源
By 佚名提供