Aragorn's Story HDU – 3966 -树剖模板

HDU – 3966

思路 ：树链剖分就是可以把一个路径上的点映射成几段连续的区间上。这样对于连续的区间可以用线段树维护，

对于每一段连续的区间都可以通过top [ ]数组很快的找到这段连续区间的头。跳的过程类似于 lca ，但这里 要注意的是

每一个点只属于一条链。 (重载运算符时要注意   node 一个 新的结点，不要 乱用*this 指针)

#include<bits/stdc++.h>
using namespace std;
#define MID int m = (l+r)/2
#define maxn 56789
#define inf 0x3f3f3f3f
struct node
{
    int sum,lazy,cnt;
    node()
    {
        sum=lazy=cnt=0;
    }
    node operator+(const node &a)const
    {
        node ret;
        ret.sum=a.sum+sum;
        ret.cnt=a.cnt+cnt;
        return ret;
    }
} tree[maxn*4];
char str[12];
vector<int>edge[maxn];
int data[maxn],n,m,id[maxn],fa[maxn],u,ans;
int son[maxn],top[maxn],tid[maxn],cnt,v,ad;
int deep[maxn],siz[maxn],id_data[maxn],q;
void pushdown(int root)
{
    if(tree[root].lazy==0)return ;
    tree[root*2].lazy+=tree[root].lazy;
    tree[root*2+1].lazy+=tree[root].lazy;
    tree[root*2].sum+=tree[root*2].cnt*tree[root].lazy;
    tree[root*2+1].sum+=tree[root*2+1].cnt*tree[root].lazy;
    tree[root].lazy=0;
}
void bulid(int root,int l,int r)
{
    tree[root].lazy=0;
    if(l==r)
    {
        tree[root].sum=id_data[l];
        tree[root].cnt=1;
        return ;
    }
    MID;
    bulid(root*2,l,m);
    bulid(root*2+1,m+1,r);
    tree[root]=tree[root*2]+tree[root*2+1];
}
void updata(int root,int l,int r,int L,int R,int ad)
{
    if(r<L||l>R)return;
    if(L<=l&&r<=R)
    {
        tree[root].sum+=tree[root].cnt*ad;
        tree[root].lazy+=ad;
        return ;
    }
    pushdown(root);
    MID;
    updata(root*2,l,m,L,R,ad);
    updata(root*2+1,m+1,r,L,R,ad);
    tree[root]=tree[root*2]+tree[root*2+1];
}
void query(int root,int l,int r,int L,int R)
{
    if(r<L||l>R)return ;
    if(L<=l&&r<=R)
    {
        ans+=tree[root].sum;
        return;
    }
    pushdown(root);
    MID;
    query(root*2,l,m,L,R);
    query(root*2+1,m+1,r,L,R);
}
void dfs1(int u,int pre,int ide)
{
    son[u]=-1,siz[u]=1;
    deep[u]=ide,fa[u]=pre;
    for(int i=0; i<edge[u].size(); i++)
    {
        int v=edge[u][i];
        if(v==pre)continue;
        dfs1(v,u,ide+1);
        if(son[u]==-1||siz[son[u]]<siz[v])
            son[u]=v;
    }
}
void dfs2(int u,int tp)
{
    top[u]=tp, tid[u]=++cnt;
    id_data[cnt]=data[u];
    if(son[u]!=-1)dfs2(son[u],tp);
    for(int i=0; i<edge[u].size(); i++)
    {
        int v=edge[u][i];
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
void solve(int x,int y,int ad)
{
    int tx=top[x],ty=top[y];
    while(tx!=ty)
    {
        if(deep[tx]<deep[ty])swap(x,y),swap(tx,ty);
        updata(1,1,n,tid[tx],tid[x],ad);
        x=fa[tx],tx=top[x];
    }
    if(deep[x]<deep[y])swap(x,y);
    updata(1,1,n,tid[y],tid[x],ad);
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&q))
    {
        cnt=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&data[i]);
            edge[i].clear();
        }
        while(m--)
        {
            scanf("%d%d",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        dfs1(1,0,1);
        dfs2(1,1);
        bulid(1,1,n);
        while(q--)
        {
            scanf("%s",str);
            if(str[0]=='I')
            {
                scanf("%d%d%d",&u,&v,&ad);
                solve(u,v,ad);
            }
            else if(str[0]=='D')
            {
                scanf("%d%d%d",&u,&v,&ad);
                solve(u,v,-ad);
            }
            else
            {
                scanf("%d",&u);
                ans=0;
                query(1,1,n,tid[u],tid[u]);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}