CDOJ1590-dfs+树链剖分（2017 UESTC Training for Data Structures O）

布满荆棘的人生 2022-06-13 09:18 122阅读 0赞

**传送门：[CDOJ1590][]**

**题目大意：**

给你一颗n个节点的树，根为T，初始时所有节点的值为0，然后给你m次操作，三种操作

1，更新一个子树，节点a的子树节点都加上b

2，更新一条树链，将从u-v的所有节点都加上c

3，查询节点的值

**题目思路：**

这题更新子树很容易想到dfs序，更新树链很容易想到树链剖分，但是如果我们理解树链剖分

的话就知道树链剖分建立重链的过程就是按照dfs序的过程，所以我们在连接重链哪里用个数组

记录子树结束的时间戳，所以在更新子树的时候就按照dfs的方法更新区间\[in\[a\],out\[a\]\]\]，树链就是

树链剖分的方法，

**AC代码：**

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 2e5+100;
    
    int n,m,T;
    int val[maxn];
    //邻接表
    struct st
    {
        int v,nex;
    }edge[maxn<<2];
    
    int hed[maxn],e;
    
    void add(int u,int v)
    {
        edge[e].v = v,edge[e].nex = hed[u],hed[u] = e++;
    }
    
    //树链剖分
    
    int Deep[maxn],Size[maxn],fa[maxn],Son[maxn],top[maxn],in[maxn],out[maxn],rk[maxn];
    int tid;
    
    void dfs1(int u,int f,int d)
    {
        Deep[u] = d;
        fa[u] = f;
        Size[u] = 1;
        for(int i=hed[u];~i;i=edge[i].nex)
        {
            int v = edge[i].v;
            if(v!=f)
            {
                dfs1(v,u,d+1);
                Size[u]+=Size[v];
                if(Son[u]==-1||Size[v]>Size[Son[u]])
                {
                    Son[u] = v;
                }
            }
        }
    }
    
    
    void dfs2(int u,int t)
    {
        top[u] = t;
        in[u] = ++tid;  //开始的时间戳
        rk[tid] = u;
        if(Son[u]!=-1)
        {
            dfs2(Son[u],t);
            for(int i=hed[u];~i;i=edge[i].nex)
            {
                int v = edge[i].v;
                if(v!=Son[u]&&v!=fa[u])
                    dfs2(v,v);
            }
    
        }
        out[u] = tid;   //结束的时间戳
    }
    
    //线段树
    int Tree[maxn<<2],c[maxn<<2];
    
    void Build(int l,int r,int rt)
    {
        c[rt] = 0;
        if(l==r)
        {
            Tree[rt] = 0;
            return ;
        }
        int mid = (l+r)>>1;
        Build(l,mid,rt<<1);
        Build(mid+1,r,rt<<1|1);
        Tree[rt] = Tree[rt<<1]=Tree[rt<<1|1];
    }
    
    void pushdown(int rt,int m)
    {
        if(c[rt])
        {
            c[rt<<1]+=c[rt];
            c[rt<<1|1]+=c[rt];
            Tree[rt<<1]+=(m-m/2)*c[rt];
            Tree[rt<<1|1]+=(m/2)*c[rt];
            c[rt] = 0;
        }
    
    }
    
    void updata(int L,int R,int l,int r,int rt,int v)
    {
        if(L<=l&&r<=R)
        {
            c[rt]+=v;
            Tree[rt]+=(r-l+1)*v;
    
            return ;
        }
        pushdown(rt,r-l+1);
        int mid = (l+r)>>1;
        if(L<=mid)updata(L,R,l,mid,rt<<1,v);
        if(R>mid)updata(L,R,mid+1,r,rt<<1|1,v);
        Tree[rt] = Tree[rt<<1]+Tree[rt<<1|1];
    }
    
    int quary(int l,int r,int rt,int pos)
    {
       if(l==r)
       {
           return Tree[rt];
       }
       pushdown(rt,r-l+1);
       int mid = (l+r)>>1;
       if(pos<=mid)return quary(l,mid,rt<<1,pos);
       else return quary(mid+1,r,rt<<1|1,pos);
    }
    
    
    
    //运行
    
    
    void change(int x,int y,int v)
    {
        while(top[x]!=top[y])
        {
            if(Deep[top[x]]<Deep[top[y]])swap(x,y);
            updata(in[top[x]],in[x],1,n,1,v);
            x = fa[top[x]];
        }
        if(Deep[x]>Deep[y])swap(x,y);
        updata(in[x],in[y],1,n,1,v);
    
    }
    
    void init()
    {
        tid = e = 0;
        memset(hed,-1,sizeof(hed));
        memset(Son,-1,sizeof(Son));
    }
    
    int main()
    {
        init();
        cin>>n>>m>>T;
        for(int i=1;i<n;i++)
        {
            int u,v;scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        dfs1(T,T,1);
        dfs2(T,T);
        Build(1,n,1);
        while(m--)
        {
            int k;scanf("%d",&k);
            int a,b,c;
            if(k==1)
            {
                scanf("%d%d",&a,&b);
                updata(in[a],out[a],1,n,1,b);
            }
            else if(k==2)
            {
                scanf("%d%d%d",&a,&b,&c);
                change(a,b,c);
            }
            else
            {
                scanf("%d",&a);
                printf("%d\n",quary(1,n,1,in[a]));
            }
        }
        return 0;
    }

[CDOJ1590]: http://acm.uestc.edu.cn/#/problem/show/1590