[HAOI2015]树上操作

[HAOI2015]树上操作(看注释)

题目描述

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：

• 操作 1 ：把某个节点 x 的点权增加 a 。
• 操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
• 操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

输入格式

第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数，表示树中节点的初始权值。
接下来 N-1 行每行两个正整数 from, to ， 表示该树中存在一条边 (from, to) 。
再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。

输出格式

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

样例 #1

样例输入 #1

5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3

样例输出 #1

6
9
13

提示

对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。

#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 时间戳
//dfs序是能够反映树上的点连续的信息的，链就是dfs序
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
    dfsxu[k]=ss[u];//存好dfs序
    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){
    //到达叶子结点，更新并返回
        tree[u].sum=dfsxu[l];
		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;
}
int querycc(int a,int b){
    
    int k=0;
    while(top[a]!=top[b]){
    //找LCA：当x,y不在同一条重链，比较x,y所在重链链首的深度大小
        if(deep[top[a]]<deep[top[b]]) swap(a,b);//确保较深
        k+=query(id[top[a]],id[a],1);//通过爬lca时每次跳链头来区间修改或查询
        a=fa[top[a]];//较深的那个沿着重链跳到链首的父亲处
    }
    if(deep[a]>deep[b]) swap(a,b);//在一条重链上就能直接操作了
    k+=query(id[a],id[b],1);
    return k;
}
signed main(){
    
    int x,y,z;
	memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&ss[i]);
    for(int i=1;i<n;i++){
    
        scanf("%lld%lld",&x,&y);
        add(x,y),add(y,x);
    }
    dfs1(1,0),dfs2(1,1);
    build(1,n,1);
    while(m--){
    
        scanf("%lld",&z);
        if(z==1){
    
            scanf("%lld%lld",&x,&y);
            update(id[x],id[x],1,y);
        }
        else if(z==2){
    
            scanf("%lld%lld",&x,&y);
            update(id[x],id[x]+size[x]-1,1,y);
        }
        else if(z==3){
    
            scanf("%lld",&x);
            printf("%lld\n",querycc(x,1));
        }
    }
}