树链剖分——模板题hdu3966

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define maxn 50005

struct Edge{int to,nxt;}edge[maxn<<];

int head[maxn],tot,n,m,q,v[maxn];

void init(){memset(head,-,sizeof head);tot=;}

void addedge(int u,int v){edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;}

int f[maxn],size[maxn],d[maxn],son[maxn];

void dfs1(int x,int pre,int deep){

    size[x]=;d[x]=deep;f[x]=pre;

    for(int i=head[x];i!=-;i=edge[i].nxt){

        int y=edge[i].to;

        if(y==pre)continue;

        dfs1(y,x,deep+);

        size[x]+=size[y];

        if(size[y]>size[son[x]])son[x]=y;

    }

}

int top[maxn],id[maxn],rk[maxn],cnt;

void dfs2(int x,int tp){

    top[x]=tp;id[x]=++cnt;rk[cnt]=x;

    if(son[x])dfs2(son[x],tp);

    for(int i=head[x];i!=-;i=edge[i].nxt){

        int y=edge[i].to;

        if(y!=son[x] && y!=f[x])dfs2(y,y);

    }

}

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

int lazy[maxn<<];

void pushdown(int rt){

    if(lazy[rt]){

        lazy[rt<<]+=lazy[rt];lazy[rt<<|]+=lazy[rt];

        lazy[rt]=;

    }

}

void update(int L,int R,int l,int r,int rt,int c){

    if(L<=l && R>=r){lazy[rt]+=c;return;}

    int m=l+r>>;

    pushdown(rt);

    if(L<=m)update(L,R,lson,c);

    if(R>m)update(L,R,rson,c);

}

int query(int pos,int l,int r,int rt){

    if(l==r)return lazy[rt]+v[rk[l]];

    pushdown(rt);

    int m=l+r>>;

    if(pos<=m)return query(pos,lson);

    else return query(pos,rson);

}

void Update(int x,int y,int c){

    while(top[x]!=top[y]){

        if(d[top[x]]<d[top[y]])swap(x,y);

        update(id[top[x]],id[x],,n,,c);

        x=f[top[x]];

    }

    if(id[x]>id[y])swap(x,y);

    update(id[x],id[y],,n,,c);

}

int main(){

    while(scanf("%d%d%d",&n,&m,&q)==){

        init();int x,y,z;char op[];

        for(int i=;i<=n;i++)scanf("%d",&v[i]);

        for(int i=;i<n;i++){scanf("%d%d",&x,&y);addedge(x,y);addedge(y,x);}

        memset(son,,sizeof son);memset(f,,sizeof f);

        cnt=;dfs1(,,);dfs2(,);

        memset(lazy,,sizeof lazy);

        while(q--){

            scanf("%s",&op);

            if(op[]=='I'){scanf("%d%d%d",&x,&y,&z);Update(x,y,z);}

            if(op[]=='D'){scanf("%d%d%d",&x,&y,&z);Update(x,y,-z);}

            if(op[]=='Q'){scanf("%d",&x);cout<<query(id[x],,n,)<<'\n';}

        }

    }

    return ;

}