shoi 魔法树

Harry Potter新学了一种魔法：可以改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法
术。这棵果树共有N个节点，其中节点0是根节点，每个节点u的父亲记为fa[u]，保证有fa[u]<u。初始时，这棵果
树上的果子都被Dumbledore用魔法清除掉了，所以这个果树的每个节点都没有果子（即0个果子）不幸的是，Harry
的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry的魔法可以
这样描述：Add u v d，表示将节点u和v之间的路径上的所有节点的果子个数都加上d。接下来，为了方便检验Harr
y的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：Query u，表示当前果树中，以点u
为根的子树中，总共有多少个果子？
Input
第一行一个整数N（1≤N≤100000），表示果树的节点总数，节点以0,1，...，N-1标号，0一定代表根节点。
接下来N-1行，每行两个整数a,b（0≤a接下来是一个整数Q（1≤Q≤100000），表示共有Q次操作。
后面跟着Q行，每行是以下两种中的一种：
1. A u v d，表示将u到v的路径上的所有节点的果子数加上d；（0≤u,v≤N-1，0<d<100000）
2. Q u，表示询问以u为根的子树中的总果子数，注意包括u本身的。（0≤u≤N-1）
1≤N≤100000，1≤Q≤100000
Output
输出询问的答案。
Sample Input
4
0 1
1 2
2 3
4
A 1 3 1
Q 0
Q 1
Q 2
Sample Output
3
3
2

//记下dfs序，就知道子树的范围了

//对一段范围进行加值，lazy操作

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <algorithm>

#include <stdlib.h>

#include <math.h>

#include <vector>

using namespace std;

typedef long long ll;

const int N=100001;

int e[N*2],nxt[N*2],head[N];

int dep[N],fa[N],siz[N],w[N],top[N],son[N],End[N];

struct A{

    ll sum,tag;

}t[N*4];

int n,C=0,edge=0;

void add(int x,int y)

{

    e[++edge]=y;

    nxt[edge]=head[x];

    head[x]=edge;

}

void dfs1(int x,int f,int d)

{//求size,dep,son,fa

    dep[x]=d;fa[x]=f;siz[x]=1;

    int i,tp=0;

    for(i=head[x];i;i=nxt[i])

        if(e[i]!=fa[x])

        {

            dfs1(e[i],x,d+1);

            siz[x]+=siz[e[i]];

            if(siz[e[i]]>tp){tp=siz[e[i]];son[x]=e[i];}

        }

}

void dfs2(int x,int tp)

{//求dfs序,链的顶端节点

    w[x]=++C;

	top[x]=tp;

    if(son[x])

	dfs2(son[x],top[x]);

    for(int i=head[x];i;i=nxt[i])

        if(e[i]!=son[x]&&e[i]!=fa[x])

            dfs2(e[i],e[i]);

    End[x]=C;//x所在子树的最大dfs序

}

void build(int x,int l,int r)

{//建立线段树

    t[x].tag=t[x].sum=0;

    if(l==r) return;

    int M=l+r>>1;

    build(x<<1,l,M);

    build(x<<1|1,M+1,r);

}

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

{//在线段树中下传标记

    if(t[x].tag)

    {

        t[x<<1].tag+=t[x].tag;

        t[x<<1|1].tag+=t[x].tag;

        int M=l+r>>1;

        t[x<<1].sum+=(M-l+1)*t[x].tag;

        t[x<<1|1].sum+=(r-M)*t[x].tag;

        t[x].tag=0;

    }

}

void update(int x,int l,int r,int ql,int qr,int v)

{//在线段树中更新[ql,qr]节点权值加v

    if(ql<=l&&qr>=r)

     {

        t[x].sum+=(r-l+1)*v;

        t[x].tag+=v;

        return;

     }

    pushdown(x,l,r);

    int M=l+r>>1;

    if(ql<=M)

	   update(x<<1,l,M,ql,qr,v);

    if(qr>M)

	   update(x<<1|1,M+1,r,ql,qr,v);

    t[x].sum=t[x<<1].sum+t[x<<1|1].sum;

}

ll query(int x,int l,int r,int ql,int qr)

{//在线段树中查询[ql,qr]的权值和

    if(ql<=l&&qr>=r) return t[x].sum;

    pushdown(x,l,r);

    int M=l+r>>1;ll sum=0;

    if(ql<=M) sum+=query(x<<1,l,M,ql,qr);

    if(qr>M) sum+=query(x<<1|1,M+1,r,ql,qr);

    return sum;

}

void upd(int x,int y,int z)

{//修改操作,见课件

    int f1=top[x],f2=top[y],tmp;

    while(f1!=f2)

    {

        if(dep[f1]<dep[f2])

        {

            tmp=f1;f1=f2;f2=tmp;

            tmp=x;x=y;y=tmp;

        }

        update(1,1,n,w[f1],w[x],z);

        x=fa[f1];

		f1=top[x];

    }

    if(dep[x]<dep[y]){tmp=x;x=y;y=tmp;}

    update(1,1,n,w[y],w[x],z);  //注意这一句，本题是对点权进行操作

}

int main()

{

    int i,x,y,m,z;char c;

    scanf("%d",&n);

    for(i=1;i<n;i++)

    {

        scanf("%d %d",&x,&y);x++;y++;

        add(x,y);

		add(y,x);

    }

    dfs1(1,-1,1);

    dfs2(1,1);

    build(1,1,n);

    scanf("%d",&m);

    for(i=1;i<=m;i++)

    {

        scanf("\n%c",&c);

        if(c=='A')

        {

            scanf("%d %d %d",&x,&y,&z);x++;y++;

            upd(x,y,z);

        }

        else

        {

            scanf("%d",&x);//统计以x为根的子树的权值

			x++;

            printf("%lld\n",query(1,1,n,w[x],End[x]));

        }

    }

    return 0;

}

巴特西

shoi 魔法树

最新文章

热门文章