Description

别忘了这是一棵动态树, 每时每刻都是动态的. 小明要求你在这棵树上维护两种事件
事件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
13

HINT

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

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

解法：树链剖分，线段树维护。为何第一次写的代码一直挂，推了重写了就过了。

///BZOJ 2589 #include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
struct edge{int v,next;}E[maxn*2];
struct seg{int l,r,sum,tag[2],ret;}tree[maxn*4];
int n, m, x, y, cnt, tim, op, l[maxn], r[maxn], dep[maxn];
int fa[maxn], siz[maxn], son[maxn], head[maxn], top[maxn];
void init(){
    memset(head, -1, sizeof(head));
    memset(son, -1, sizeof(son));
    tim=cnt=0;
}
void add(int u, int v){
    E[cnt].v=v,E[cnt].next=head[u],head[u]=cnt++;
}
void dfs1(int u, int father, int d){
    dep[u]=d;
    fa[u]=father;
    siz[u]=1;
    for(int i=head[u];~i;i=E[i].next){
        int v=E[i].v;
        if(v==father) continue;
        dfs1(v,u,d+1);
        siz[u]+=siz[v];
        if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u, int tp){
    top[u]=tp;
    l[u]=++tim;
    r[u]=tim;
    if(son[u]==-1) return;
    dfs2(son[u],tp);
    for(int i=head[u];~i;i=E[i].next){
        int v=E[i].v;
        if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
    }
    r[u]=tim;
}
void pushup(int rt){
    tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;
    tree[rt].ret=tree[rt*2].ret+tree[rt*2+1].ret;
}
void build(int l, int r, int rt){
    tree[rt].l=l,tree[rt].r=r,tree[rt].tag[0]=-1;
    if(l==r) return;
    int mid=(l+r)/2;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
}
void update1(int rt, int z){
    tree[rt].tag[1]+=z;
    tree[rt].sum+=z*(tree[rt].r-tree[rt].l+1);
}
void update2(int rt, int z){
    tree[rt].tag[0]=z;
    tree[rt].ret=tree[rt].sum*z;
}
void pushdown(int rt){
    if(tree[rt].tag[1]){
        update1(rt*2,tree[rt].tag[1]);
        update1(rt*2+1,tree[rt].tag[1]);
        tree[rt].tag[1]=0;
    }
    if(tree[rt].tag[0]!=-1){
        update2(rt*2,tree[rt].tag[0]);
        update2(rt*2+1,tree[rt].tag[0]);
        tree[rt].tag[0]=-1;
    }
}
void change(int x, int y, int z, int rt){
    if(tree[rt].tag[0]==z) return;
    if(tree[rt].l==x&&tree[rt].r==y){update2(rt,z);return;}
    int mid=(tree[rt].l+tree[rt].r)/2;
    pushdown(rt);
    if(y<=mid) change(x,y,z,rt*2);
    else if(x>mid) change(x,y,z,rt*2+1);
    else{
        change(x,mid,z,rt*2);
        change(mid+1,y,z,rt*2+1);
    }
    pushup(rt);
}
void add(int x, int y, int z, int rt){
    if(tree[rt].l==x&&tree[rt].r==y){update1(rt,z);return;}
    int mid=(tree[rt].l+tree[rt].r)/2;
    pushdown(rt);
    if(y<=mid) add(x,y,z,rt*2);
    else if(x>mid) add(x,y,z,rt*2+1);
    else{
        add(x,mid,z,rt*2);
        add(mid+1,y,z,rt*2+1);
    }
    pushup(rt);
}
void solve(int x, int y, int z){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        change(l[top[x]],l[x],z,1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    change(l[x],l[y],z,1);
}
int main(){
    scanf("%d", &n);
    init();
    for(int i=1; i<n; i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs1(1,1,1);
    dfs2(1,1);
    build(1,n,1);
    scanf("%d", &m);
    while(m--){
        int op,x,u,v;
        scanf("%d%d",&op,&x);
        if(op){
            for(int i=1; i<=x; i++){
                scanf("%d%d", &u,&v);
                solve(u,v,1);
            }
            printf("%d\n", tree[1].ret&((1<<31)-1));
            update2(1,0);
        }
        else{
            scanf("%d", &u);
            add(l[x],r[x],u,1);
        }
    }
    return 0;
}