(重链剖分)魔法树

[SHOI2012]魔法树(过程全在注释)

题目背景

SHOI2012 D2T3

题目描述

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

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

不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：A u v d 。表示将点 $u$ 和 $v$ 之间的路径上的所有节点的果子个数都加上 $d$。

接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：Q u。表示当前果树中，以点 $u$ 为根的子树中，总共有多少个果子？

输入格式

第一行一个正整数 $N(1\le N\le 100000)$，表示果树的节点总数，节点以 $0,1,\dots ,N-1$ 标号，$0$ 一定代表根节点。

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

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

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

1. A u v d，表示将 $u$ 到 $v$ 的路径上的所有节点的果子数加上 $d$。保证 $0\le u,v<N,0<d<100000$

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

3
3
2

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int head[N],cnt;
int fa[N],size[N],deep[N],son[N],top[N],dfsxu[N],id[N],k;
//fa[i] 节点i的父节点 size[i] 以i为根的子树总节点数
//deep[i] 节点i的深度 son[i] 节点i的重儿子
//top[i] 节点i所在的重链的最顶上元素
//dfsxu 各点初始值 id 时间戳
int n,v[N],m,r,ss[N];
struct stu{
    
    int l,r,sum,lz;
}tree[N*4];
struct stuu{
    
	int to,nt;
}ed[N*2];
void add(int u,int v){
    //链式前向星加边
	ed[cnt]=stuu{
    v,head[u]};
	head[u]=cnt++;
}
void dfs1(int u,int f){
    //u为当前节点,f为当前节点的父节点；初始化1
    fa[u]=f;//u节点的父节点是f
    deep[u]=deep[f]+1;//深度+1
    size[u]=1;
    int maxsize=-1;//判断是不是重儿子的临时变量
    for(int i=head[u];i!=-1;i=ed[i].nt){
    //遍历所有儿子，不断更新同时找到重儿子
		int v=ed[i].to;
        if(v==f) continue;//是父亲肯定直接跳过
        dfs1(v,u);//深度遍历,当前节点变为父节点，找到的儿子变为当前节点继续遍历下去
        size[u]+=size[v];//遍历完成后，让当前节点的大小加上儿子的大小
        if(size[v]>maxsize){
    //如果儿子的大小大于临时变量
            maxsize=size[v];//就赋给临时变量
            son[u]=v;//更改当前节点的重儿子
        }
    }
}
void dfs2(int u,int t){
    //初始化2
    id[u]=++k;//每到了一个节点赋时间戳
    top[u]=t;//节点u所在重链的顶端是t
    if(!son[u]) return;//没有重儿子就没儿子了直接返回
    dfs2(son[u],t);//继续往重儿子走
    for(int i=head[u];i!=-1;i=ed[i].nt){
    
        int v =ed[i].to;
        if(v==fa[u]||v==son[u]) continue;//如果是父节点或重儿子直接跳过
        dfs2(v,v);//一些重链从轻儿子开始往下有,顶部是轻儿子
    }
}
void pushup(int u){
    //向上更新
    tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;//左右两子段的区间和相加反馈给顶部
}
void pushdown(int u){
    //向下更新，将lazy标向下推
    if(tree[u].lz){
    
        tree[u<<1].sum+=tree[u].lz*(tree[u<<1].r-tree[u<<1].l+1);
        tree[u<<1|1].sum+=tree[u].lz*(tree[u<<1|1].r-tree[u<<1|1].l+1);
        tree[u<<1].lz+=tree[u].lz;
        tree[u<<1|1].lz+=tree[u].lz;
        tree[u].lz=0;
    }
}
void build(int l,int r,int u){
    //建树
    tree[u].l=l,tree[u].r=r;
	if(l==r){
    //到达叶子结点，更新并返回
		return ;
	}//否则这个结点代表的不止一个点，它还有两个儿子
	int mid=(l+r)>>1;
	build(l,mid,u<<1);//递归左子树
	build(mid+1,r,u<<1|1);//递归右子树
	pushup(u);//更新
}
void update(int l,int r,int u,int b){
    
    if(l<=tree[u].l&&tree[u].r<=r){
    //作为子区间被包含，则进行整体修改，不继续深入
        tree[u].sum+=b*(tree[u].r-tree[u].l+1);
        tree[u].lz+=b;
        return ;
    }//否则处于交错，则需要继续深入更底层子区间
    pushdown(u);//向下更新
    int mid=(tree[u].l+tree[u].r)>>1;
	if(l<=mid) update(l,r,u<<1,b);//递归左子树
	if(r>=mid+1) update(l,r,u<<1|1,b);//递归右子树
	pushup(u);//更新
}
int query(int l,int r,int u){
    
    if(l<=tree[u].l&&tree[u].r<=r){
    //作为子区间被包含，则进行整体修改，不继续深入
        return tree[u].sum;
    }//否则处于交错，则需要继续深入更底层子区间
    int k=0;
	int mid=(tree[u].l+tree[u].r)>>1;//折半查找
    pushdown(u);//向下更新
	if(l<=mid) k+=query(l,r,u<<1);//询问的一部分在左儿子的管辖范围内
	if(r>=mid+1) k+=query(l,r,u<<1|1);//一部分在右儿子范围内
	return k;
}
void updatecc(int a,int b,int c){
    
    while(top[a]!=top[b]){
    //找LCA：当x,y不在同一条重链，比较x,y所在重链链首的深度大小
        if(deep[top[a]]<deep[top[b]]) swap(a,b);//确保较深
        update(id[top[a]],id[a],1,c);//通过爬lca时每次跳链头来区间修改或查询
        a=fa[top[a]];//较深的那个沿着重链跳到链首的父亲处
    }
    if(deep[a]>deep[b]) swap(a,b);
    update(id[a],id[b],1,c);
}
signed main(){
    
	memset(head,-1,sizeof(head));
    cin>>n;
    int u,v,p;
    for(int i=1;i<n;i++){
    
        scanf("%lld%lld",&u,&v);
        ++u,++v;
        add(u,v),add(v,u);
    }
    dfs1(1,0),dfs2(1,1);
    build(1,n,1);
    cin>>m;
    while(m--){
    
        char k;
        cin>>k;
        if(k=='A'){
    
            scanf("%lld%lld%lld",&u,&v,&p);
            ++u,++v;
            updatecc(u,v,p);
        }
        else{
    
            scanf("%lld",&p);
            p++;
            printf("%lld\n",query(id[p],id[p]+size[p]-1,1));
        }
    }
    return 0;
}