【SHOI2012】魔法树

题面

BZOJ上找不到这道题目

只有洛谷上有。。

所以粘贴洛谷的题面

题解

树链剖分之后直接维护线段树就可以了

树链剖分良心模板题

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAX 110000

#define lson (now<<1)

#define rson (now<<1|1)

#define ll long long

inline int read()

{

    register int x=0,t=1;

    register char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-'){t=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}

    return x*t;

}

struct Node

{

    long long s;

    long long ly;

}t[MAX<<2];

int tim;

struct Line

{

    int v,next;

}e[MAX];

int h[MAX],cnt=1;

int dfn[MAX],low[MAX],dep[MAX],ff[MAX],size[MAX],hson[MAX],top[MAX];

int line[MAX],N;

inline void Add(int u,int v)

{

    e[cnt]=(Line){v,h[u]};

    h[u]=cnt++;

}

void DFS1(int u)

{

    dep[u]=dep[ff[u]]+1;size[u]=1;

    for(int i=h[u];i;i=e[i].next)

    {

        int v=e[i].v;

        DFS1(v);

        if(size[v]>size[hson[u]])hson[u]=v;

        size[u]+=size[v];

    }

}

void DFS2(int u,int tp)

{

    top[u]=tp;dfn[u]=++tim;line[tim]=u;

    if(hson[u])DFS2(hson[u],tp);

    for(int i=h[u];i;i=e[i].next)

    {

        int v=e[i].v;

        if(v==hson[u])continue;

        DFS2(v,v);

    }

    low[u]=tim;

}

void pushup(int now)

{

    t[now].s=t[lson].s+t[rson].s;

}

void putlazy(int now,int ly,int l,int r)

{

    t[now].s+=1LL*(r-l+1)*ly;

    t[now].ly+=ly;

}

void pushdown(int now,int l,int r)

{

    int mid=(l+r)>>1;

    putlazy(lson,t[now].ly,l,mid);

    putlazy(rson,t[now].ly,mid+1,r);

    t[now].ly=0;

}

void Modify(int now,int l,int r,int al,int ar,int d)

{

    if(l==al&&r==ar){putlazy(now,d,l,r);return;}

    int mid=(l+r)>>1;

    t[now].s+=1LL*(ar-al+1)*d;

    if(ar<=mid)Modify(lson,l,mid,al,ar,d);

    else if(al>mid)Modify(rson,mid+1,r,al,ar,d);

    else {Modify(lson,l,mid,al,mid,d);Modify(rson,mid+1,r,mid+1,ar,d);}

}

ll Query(int now,int l,int r,int al,int ar)

{

    if(l==al&&r==ar)return t[now].s;

    int mid=(l+r)>>1;

    pushdown(now,l,r);

    ll re=0;

    if(ar<=mid)re=Query(lson,l,mid,al,ar);

    else if(al>mid)re=Query(rson,mid+1,r,al,ar);

    else re=Query(lson,l,mid,al,mid)+Query(rson,mid+1,r,mid+1,ar);

    pushup(now);

    return re;

}

void LCA(int u,int v,int d)

{

    while(top[u]!=top[v])

    {

        if(dep[top[u]]<dep[top[v]])swap(u,v);

        Modify(1,1,N,dfn[top[u]],dfn[u],d);

        u=ff[top[u]];

    }

    if(dep[v]>dep[u])swap(u,v);

    Modify(1,1,N,dfn[v],dfn[u],d);

}

int main()

{

    N=read();

    for(int i=1;i<N;++i)

    {

        int x=read()+1,y=read()+1;

        ff[y]=x;

        Add(x,y);

    }

    DFS1(1);DFS2(1,1);

    int Q=read();

    while(Q--)

    {

        char ch[3];scanf("%s",ch);

        if(ch[0]=='A')

        {

            int u=read()+1,v=read()+1,d=read();

            LCA(u,v,d);

        }

        else

        {

            int u=read()+1;

            printf("%lld\n",Query(1,1,N,dfn[u],low[u]));

        }

    }

    return 0;

}