BZOJ2863[SHOI2012]魔法树——树链剖分+线段树

题目描述

输入

输出

样例输入

4
0 1
1 2
2 3
4
Add 1 3 1
Query 0
Query 1
Query 2

样例输出

3
3
2

 

　　树链剖分模板题，路径修改子树查询，注意节点编号从零开始，答案爆int。

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,m;
int num;
int tot;
int ans;
int x,y,z;
char ch[10];
ll a[800010];
int s[100010];
int t[100010];
int d[100010];
int f[100010];
int to[100010];
ll sum[800010];
int son[100010];
int top[100010];
int head[100010];
int next[100010];
int size[100010];
void add(int x,int y)
{
    tot++;
    next[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
void dfs(int x)
{
    size[x]=1;
    d[x]=d[f[x]]+1;
    for(int i=head[x];i;i=next[i])
    {
        dfs(to[i]);
        size[x]+=size[to[i]];
        if(size[to[i]]>size[son[x]])
        {
            son[x]=to[i];
        }
    }
}
void dfs2(int x,int tp)
{
    s[x]=++num;
    top[x]=tp;
    if(son[x])
    {
        dfs2(son[x],tp);
    }
    for(int i=head[x];i;i=next[i])
    {
        if(to[i]!=son[x])
        {
            dfs2(to[i],to[i]);
        }
    }
    t[x]=num;
}
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,int l,int r)
{
    if(a[rt])
    {
        int mid=(l+r)>>1; 
        a[rt<<1]+=a[rt];
        a[rt<<1|1]+=a[rt];
        sum[rt<<1]+=(mid-l+1)*a[rt];
        sum[rt<<1|1]+=(r-mid)*a[rt];
        a[rt]=0;
    }
}
void change(int rt,int l,int r,int L,int R,int v)
{
    if(L<=l&&r<=R)
    {
        sum[rt]+=(r-l+1)*v;
        a[rt]+=v;
        return ;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)
    {
        change(rt<<1,l,mid,L,R,v);
    }
    if(R>mid)
    {
        change(rt<<1|1,mid+1,r,L,R,v);
    }
    pushup(rt);
}
ll query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
    {
        return sum[rt];
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    ll res=0;
    if(L<=mid)
    {
        res+=query(rt<<1,l,mid,L,R);
    }
    if(R>mid)
    {
        res+=query(rt<<1|1,mid+1,r,L,R);
    }
    return res;
}
void lca(int x,int y,int v)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]])
        {
            swap(x,y);
        }
        change(1,1,n,s[top[x]],s[x],v);
        x=f[top[x]];
    }
    if(d[x]>d[y])
    {
        swap(x,y);
    }
    change(1,1,n,s[x],s[y],v);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        x++;
        y++;
        f[y]=x;
        add(x,y);
    }
    dfs(1);
    dfs2(1,1);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",ch);
        if(ch[0]=='A')
        {
            scanf("%d%d%d",&x,&y,&z);
            x++;
            y++;
            lca(x,y,z);
        }
        else
        {
            scanf("%d",&x);
            x++;
            printf("%lld
",query(1,1,n,s[x],t[x]));
        }
    }
}