树链剖分【P3833】 [SHOI2012]魔法树

Description

Harry Potter 新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。

这棵果树共有N个节点，其中节点0是根节点，每个节点u的父亲记为fa[u]，保证有fa[u] < u。初始时，这棵果树上的果子都被 Dumbledore 用魔法清除掉了，所以这个果树的每个节点上都没有果子（即0个果子）。

不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：

Add u v d

表示将点u和v之间的路径上的所有节点的果子个数都加上d。

接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：

Query u

表示当前果树中，以点u为根的子树中，总共有多少个果子？

Input

第一行一个正整数N (1 ≤ N ≤ 100000)，表示果树的节点总数，节点以0,1,…,N − 1标号，0一定代表根节点。

接下来N − 1行，每行两个整数a,b (0 ≤ a < b < N)，表示a是b的父亲。

接下来是一个正整数Q(1 ≤ ? ≤ 100000)，表示共有Q次操作。

后面跟着Q行，每行是以下两种中的一种：

A u v d，表示将u到v的路径上的所有节点的果子数加上d；0 ≤ u,v <N,0 < d < 100000

Q u，表示询问以u为根的子树中的总果子数，注意是包括u本身的。

Output

对于所有的Query操作，依次输出询问的答案，每行一个。答案可能会超过2^32 ，但不会超过10^15 。

刚刚学树剖练练手,一个树剖裸题,线段树不需要建树.

话说省选竟然会考模板题emm

PS:数组开大,开$long \ long $，还有记得用字符串读入,不要用单个字符。

代码

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

#define int long long

#define R register

#define ls o<<1

#define rs o<<1|1

#define N 200008

using namespace std;

inline void in(int &x)

{

    int f=1;x=0;char s=getchar();

    while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

    while(isdigit(s)){x=x*10+s-'0';s=getchar();}

    x*=f;

}

int n,head[N],tot,depth[N],size[N],son[N],dfn[N],fdfn[N],f[N];

struct cod{int u,v;}edge[N<<1];

int idx,m,top[N],tr[N<<2],tg[N<<2];

inline void add(int x,int y)

{

    edge[++tot].u=head[x];

    edge[tot].v=y;

    head[x]=tot;

}

void dfs1(int u,int fa)

{

    depth[u]=depth[fa]+1;size[u]=1;f[u]=fa;

    for(R int i=head[u];i;i=edge[i].u)

    {

        if(edge[i].v==fa)continue;

        dfs1(edge[i].v,u);

        size[u]+=size[edge[i].v];

        if(son[u]==-1 or size[son[u]]<size[edge[i].v])

            son[u]=edge[i].v;

    }

}

void dfs2(int u,int t)

{

    top[u]=t;dfn[u]=++idx;fdfn[idx]=u;

    if(son[u]==-1)return;

    dfs2(son[u],t);

    for(R int i=head[u];i;i=edge[i].u)

    {

        if(dfn[edge[i].v])continue;

        dfs2(edge[i].v,edge[i].v);

    }

}

inline void down(int o,int l,int r)

{

    if(tg[o])

    {

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

        tg[ls]+=tg[o];tg[rs]+=tg[o];

        tr[ls]+=(mid-l+1)*tg[o];tr[rs]+=(r-mid)*tg[o];

        tg[o]=0;

    }

}

void change(int o,int l,int r,int x,int y,int z)

{

    if(x<=l and y>=r)

    {

        tr[o]+=(r-l+1)*z;

        tg[o]+=z;

        return;

    }

    down(o,l,r);

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

    if(x<=mid)change(ls,l,mid,x,y,z);

    if(y>mid)change(rs,mid+1,r,x,y,z);

    tr[o]=tr[ls]+tr[rs];

}

int query(int o,int l,int r,int x,int y)

{

    if(x<=l and y>=r)return tr[o];

    down(o,l,r);

    int mid=(l+r)>>1,res=0;

    if(x<=mid)res+=query(ls,l,mid,x,y);

    if(y>mid)res+=query(rs,mid+1,r,x,y);

    return res;

}

inline void tchange(int x,int y,int z)

{

    int fx=top[x],fy=top[y];

    while(fx!=fy)

    {

        if(depth[fx]>depth[fy])

        {

            change(1,1,idx,dfn[fx],dfn[x],z);

            x=f[fx];

        }

        else

        {

            change(1,1,idx,dfn[fy],dfn[y],z);

            y=f[fy];

        }

        fx=top[x],fy=top[y];

    }

    if(dfn[x]>dfn[y])swap(x,y);

    change(1,1,idx,dfn[x],dfn[y],z);

}

signed main()

{

    in(n);memset(son,-1,sizeof son);

    for(R int i=1,x,y;i<n;i++)

    {

        in(x),in(y);

        x++,y++;

        add(x,y);add(y,x);

    }

    dfs1(1,0);dfs2(1,1);

    in(m);

    for(R int x,y,z;m;m--)

    {

        R char opt[8];

        scanf("%s",opt);

        switch(opt[0])

        {

            case 'A':in(x),in(y),in(z);x++;y++;tchange(x,y,z);break;

            case 'Q':in(x);x++;printf("%lld\n",query(1,1,n,dfn[x],dfn[x]+size[x]-1));break;

        }

    }

}

巴特西

树链剖分【P3833】 [SHOI2012]魔法树

Description

Input

Output

最新文章

热门文章