SCUOJ4549-树链剖分（区间查询，区间更新，边权）

桃扇骨 2022-06-17 02:49 112阅读 0赞

**传送门：**[scu4559][]

Description
     
    There is a king who is very rich, but he is very stingy. In his kingdom, there are many cities. 
    He built many highways to connect all the cities. Buecause of his meanness, he would not build extra highways, that's to say, 
    there is only one path between any two cities. After building all the highways, he set a high toll for each highway. 
    But because of his greed, he sometimes will increase the tolls to get more benefits. Now the king wants to know the 
    tolls between two cities.
    However he is a fool, so he asks you to help him calculate the answer.
    
    
    
     Input
    
    The first line contains an integer T indicating the number of cases. (T < 20)
    For each case, the first line contains two integers N and M indicating the number of cities and the number of operations. (N <= 10^5, M <= 10^5)
    Then N-1 lines followed. Each line contains three integers a, b and c. It means there is a highway between city a and city b, and the toll is c. 
    (1 <= a <= n, 1 <= b <= n, a <> b, 0 < c <= 10^5)
    Then M lines followed. Each line has one of two operations.
    The first operation is "ADD a b c". which means adding c to the toll of every highway between city a and city b. (0 < c <= 10^5)
    The second is "QUERY a b", which means querying the highway tolls between city a and city b.
    
    
     Output
    
    Answer for each QUERY operation.
    
     Sample Input
    
    1
    5 3
    1 2 1
    1 3 2
    2 4 3
    2 5 4
    QUERY 1 2
    ADD 1 5 1
    QUERY 1 5
    
    
     Sample Output
    
    1
    7

**第一道树链剖分入门题，，哎，，搞了两天，，真心菜，，树链剖分详见各路大神的博客**

**题目大意：**

给你一个n个点的树，q次操作，每条边都有一个权值，有两种操作

1，QUERY x  y 查询 x到y的路径上所有的边权和

2，ADD x y w 将x到y的路径上的所有边权加上 w

**题目思路：**

树链剖分+线段树模板

基于边权的区间查询和区间更新

**AC代码：**

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<vector>
    using namespace std;
    #define ll long long
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    const int maxn = 1e5+10;
    
    struct Tree
    {
        int l,r;
        ll sum,c;
    }node[maxn*8];    //线段树
    
    struct nod
    {
        int v,nex;
        ll w;
    }edge[maxn<<1];   //图;
    
    int head[maxn];
    
    int tim ;   //记录编号
    ll val[maxn];
    int Size[maxn];  // 以x为根的子树节点个数
    int Top[maxn];  // 当前节点所在链的顶端节点
    int Son[maxn];  // 保存重儿子
    int Deep[maxn];  // 节点深度
    int Father[maxn];  // 保存父亲节点
    int Tid[maxn];  // 剖分后的新编号
    int Rank[maxn];  // 保存在线段树中的编号
    
    int n,m,e;   //节点个数和边数
    
    // 初始化函数
    
    void init()
    {
        tim = 0;
        e = 1;
        memset(head,-1,sizeof(head));
        memset(Son,-1,sizeof(Son));
    }
    
    void add(int u,int v,ll w)
    {
        edge[e].v = v,edge[e].w = w,edge[e].nex = head[u],head[u]=e++;
    }
    
    //   记录所有的重边
    void dfs(int u,int father,int d)
    {
        Deep[u]=d;
        Father[u]=father;
        Size[u]=1;
        for(int i=head[u];~i;i=edge[i].nex)
        {
            int v = edge[i].v;
            if(v!=father)
            {
                val[v] = edge[i].w;
                dfs(v,u,d+1);
                Size[u]+=Size[v];
                if(Son[u]==-1||Size[v]>Size[Son[u]])
                    Son[u]=v;
            }
        }
    }
    
    //重连边成重边
    
    void Create(int u,int top)
    {
        Top[u]=top;
        Tid[u]=++tim;
        Rank[Tid[u]] = u;
    
        if(Son[u]==-1)return ;
        Create(Son[u],top);
        for(int i=head[u];~i;i=edge[i].nex)
        {
            int v = edge[i].v;
            if(v!=Son[u]&&v!=Father[u])
                Create(v,v);
        }
    }
    
    void BuildTree(int l,int r,int rt)
    {
        node[rt].l = l,node[rt].r = r;
        node[rt].c = 0;
        if(l==r)
        {
            node[rt].sum = val[Rank[l]];
            return ;
        }
        int mid = (l+r)>>1;
        BuildTree(lson);
        BuildTree(rson);
        node[rt].sum = node[rt<<1].sum+node[rt<<1|1].sum;
    }
    
    void pushdown(int rt,ll m)
    {
        node[rt<<1].c+=node[rt].c;
        node[rt<<1|1].c+=node[rt].c;
        node[rt<<1].sum+=node[rt].c*(m-m/2);
        node[rt<<1|1].sum+=node[rt].c*(m/2);
        node[rt].c = 0;
    }
    
    ll quary(int l,int r,int rt)    //区间查询
    {
        if(l<=node[rt].l&&r>=node[rt].r)return node[rt].sum;
        if(node[rt].c)pushdown(rt,node[rt].r-node[rt].l+1ll);
        int mid = (node[rt].l+node[rt].r)>>1;
        ll res = 0;
        if(l<=mid)res+=quary(l,r,rt<<1);
        if(r>mid)res+=quary(l,r,rt<<1|1);
        return res;
    }
    
    void update(int l,int r,ll w,int rt)    //区间更新
    {
        if(l<=node[rt].l&&r>=node[rt].r)
        {
            node[rt].c+=w;
            node[rt].sum+=(node[rt].r-node[rt].l+1ll)*w;
            return ;
        }
        int mid = (node[rt].l+node[rt].r)>>1;
        if(node[rt].c)pushdown(rt,node[rt].r-node[rt].l+1ll);
        if(l<=mid)update(l,r,w,rt<<1);
        if(r>mid)update(l,r,w,rt<<1|1);
        node[rt].sum = node[rt<<1].sum+node[rt<<1|1].sum;
    }
    
    ll SUM(int x,int y)
    {
        ll res = 0;
        while(Top[x]!=Top[y])
        {
            if(Deep[Top[x]]<Deep[Top[y]])swap(x,y);
            res+=quary(Tid[Top[x]],Tid[x],1);
            x = Father[Top[x]];
        }
        if(x!=y)
        {
            if(Deep[x]<Deep[y])swap(x,y);
            res+=quary(Tid[y]+1,Tid[x],1);
        }
        return res;
    }
    
    void ADD(int x,int y,ll w)
    {
        while(Top[x]!=Top[y])
        {
            if(Deep[Top[x]]<Deep[Top[y]])swap(x,y);
            update(Tid[Top[x]],Tid[x],w,1);
            x = Father[Top[x]];
        }
        if(x!=y)
        {
            if(Deep[x]<Deep[y])swap(x,y);
            update(Tid[y]+1,Tid[x],w,1);
        }
    }
    
    int main()
    {
        int t;cin>>t;
        while(t--)
        {
            init();
            scanf("%d%d",&n,&m);
            for(int i=1;i<n;i++)
            {
                int x,y;
                ll w;
                scanf("%d%d%lld",&x,&y,&w);
                add(x,y,w);
                add(y,x,w);
            }
            dfs(1,1,1);
            Create(1,1);
            BuildTree(1,n,1);
    
            char s[10];
            while(m--)
            {
                scanf("%s",s);
                int x,y;
                ll w;
                scanf("%d%d",&x,&y);
                if(s[0]=='Q')
                {
                    printf("%lld\n",SUM(x,y));
                }
                else
                {
                    scanf("%lld",&w);
                    ADD(x,y,w);
                }
            }
        }
        return 0;
    }

[scu4559]: http://acm.scu.edu.cn/soj/problem.action?id=4549