题目描述

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为根的子树中，总共有多少个果子？

输入输出格式

输入格式：

第一行一个正整数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本身的。

输出格式：

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

输入输出样例

输入样例#1：

4 0 1 1 2 2 3 4 A 1 3 1

Q 0 Q 1 Q 2

输出样例#1：

3 3 2

solution：

又是一道树链剖分，又是一道模板题。

不会树链剖分的戳这里 

因为一棵子树在这个线段树上是连续的，所以第二个操作就迎刃而解了，直接在线段树上查询。至于第一个操作，就先让u,v跳到一条链上，在链上编号连续，所以对于同一链上的可以用线段树维护。

ADD 操作 就是这样的。

inline void change(int x,int y,int z){    int tx=top[x],ty=top[y];    while(tx!=ty){        if(dep[tx]>dep[ty])         {            swap(x,y);            swap(tx,ty);        }        update(1,num[ty],num[y],z);        y=fa[ty];ty=top[y];    }    if(x==y){        update(1,num[x],num[x],z);    }    else{        if(dep[x]>dep[y]) swap(x,y);        update(1,num[x],num[y],z);    }}

 

线段树：区间修改

inline void update(int o,int x,int y,int k){    int l=tree[o].l;    int r=tree[o].r;    if(l>=x&&r<=y)    {        tree[o].sum+=(r-l+1)*k;        add[o]+=k;        return;    }    if(x>r||l>y) return;    else    {        if(add[o]) pushup(o);        update(lc,x,y,k);        update(rc,x,y,k);        tree[o].sum=tree[lc].sum+tree[rc].sum;    }}

 

线段树：区间查询

inline long long query(int o,int x,int y){    int l=tree[o].l;    int r=tree[o].r;    if(l>=x&&r<=y)    {        return tree[o].sum;    }    if(x>r||l>y) return 0;    else    {        if(add[o]) pushup(o);        return     query(lc,x,y)+query(rc,x,y);    }}

 

下放标记及建树

inline void build(int o,int l,int r){    tree[o].l=l;    tree[o].r=r;    if(l==r){        tree[o].sum=0;        return;    }    else    {        int mid = tree[o].mid();        build(lc,l,mid);        build(rc,mid+1,r);        tree[o].sum=tree[lc].sum+tree[rc].sum;    }}inline void pushup(int o){    add[lc]+=add[o];    add[rc]+=add[o];    tree[lc].sum+=(tree[lc].r-tree[lc].l+1)*add[o];    tree[rc].sum+=(tree[rc].r-tree[rc].l+1)*add[o];    add[o]=0;}

 

完整代码

#include
     
      using namespace std;const int MAXN = 100000 + 10;inline int read(){    char ch;    int fl=1;    int xx=0;    do{      ch= getchar();      if(ch=='-')        fl=-1;    }while(ch<'0'||ch>'9');    do{        xx=(xx<<3)+(xx<<1)+ch-'0';        ch=getchar();    }while(ch>='0'&&ch<='9');    return xx*fl;}int n,q; struct node{    int to;    int next;};node g[MAXN*2];int cnt=0,head[MAXN];inline void addedge(int a,int b){    ++cnt;g[cnt].to=b;g[cnt].next=head[a];head[a]=cnt;return;}int fa[MAXN],dep[MAXN],son[MAXN],tot[MAXN];#define v g[i].toinline void dfs(int now){    son[now]=0,tot[now]=1;    for(int i=head[now];i>0;i=g[i].next){        if(v!=fa[now]){            fa[v]=now;            dep[v]=dep[now]+1;            dfs(v);            if(tot[son[now]]
      
       0;i=g[i].next)    {        if(v!=fa[now]&&v!=son[now])            dfs2(v,v);    }}struct s_tree{    int l;    int r;    long long sum;    inline int mid()    {        return (l+r)>>1;    }};s_tree tree[MAXN*4];long long add[MAXN*4];#define lc o<<1#define rc o<<1|1inline void build(int o,int l,int r){    tree[o].l=l;    tree[o].r=r;    if(l==r){        tree[o].sum=0;        return;    }    else    {        int mid = tree[o].mid();        build(lc,l,mid);        build(rc,mid+1,r);        tree[o].sum=tree[lc].sum+tree[rc].sum;    }}inline void pushup(int o){    add[lc]+=add[o];    add[rc]+=add[o];    tree[lc].sum+=(tree[lc].r-tree[lc].l+1)*add[o];    tree[rc].sum+=(tree[rc].r-tree[rc].l+1)*add[o];    add[o]=0;}inline void update(int o,int x,int y,int k){    int l=tree[o].l;    int r=tree[o].r;    if(l>=x&&r<=y)    {        tree[o].sum+=(r-l+1)*k;        add[o]+=k;        return;    }    if(x>r||l>y) return;    else    {        if(add[o]) pushup(o);        update(lc,x,y,k);        update(rc,x,y,k);        tree[o].sum=tree[lc].sum+tree[rc].sum;    }}inline void change(int x,int y,int z){    int tx=top[x],ty=top[y];    while(tx!=ty){        if(dep[tx]>dep[ty])         {            swap(x,y);            swap(tx,ty);        }        update(1,num[ty],num[y],z);        y=fa[ty];ty=top[y];    }    if(x==y){        update(1,num[x],num[x],z);    }    else{        if(dep[x]>dep[y]) swap(x,y);        update(1,num[x],num[y],z);    }}inline long long query(int o,int x,int y){    int l=tree[o].l;    int r=tree[o].r;    if(l>=x&&r<=y)    {        return tree[o].sum;    }    if(x>r||l>y) return 0;    else    {        if(add[o]) pushup(o);        return     query(lc,x,y)+query(rc,x,y);    }}int main(){     n=read();    for(int i=1;i<=n;i++)    {        head[i]=-1;    }    for(int i=1;i