树链剖分

基本概念

将树中的点重新编号,使得树中任意一条路径,都可以转化成O(logn)段连续区间
1.将一棵树转化成一个序列
2.将树中的任意一段路径转化成logn段连续区间(线段树,树状数组)

重链剖分

重儿子:子树数量最多的根节点(只有一个,多个都是,任选一个即可)
轻儿子:其余儿子
重边:重儿子和父节点的相连的边
重链:重边构成的极大路径(每个点都要包含在一个重链里面)
轻边:轻儿子和父节点相连的边

重新编号:利用dfs序给整棵树编号,要求优先遍历重儿子,即可保证重链上所有点的编号是连续的
定理:树中任意一条路径均可拆分成o(logn)个条重链,即可拆分成logn个连续区间
补充:每条重链的开头都是一个轻儿子
模板题链接

代码:

#include<bits/stdc++.h>

#define endl '\n'
#define int long long
//#define x first
//#define y second

using namespace std;

constexpr  int N=1e5+10;

typedef pair<int,int> PII;

int n,m;
vector<int> e[N];
int w[N];//点的权值 
int id[N],nw[N];//dfs序的编号,每个编号的点的权值是多少 
int cnt;
int dep[N],sz[N],top[N],fa[N],son[N];//深度,子树大小,重链的顶点,父节点,重儿子

struct Tree{//线段树辅助
	int l,r;
	int add,sum;
}tr[N*4]; 

void dfs1(int u,int dad){//预处理出每科子树的大小
	dep[u]=dep[dad]+1,sz[u]=1;
	for(auto v:e[u]){
		if(v==dad) continue;
		fa[v]=u;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v]) son[u]=v; 
	}
}

void dfs2(int u,int t){//预处理出dfs序编号,以及该编号节点的权值大小
	id[u]=++cnt,nw[cnt]=w[u],top[u]=t;
	if(!son[u]) return ;
	dfs2(son[u],t);
	for(auto v:e[u]){
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);//每条重链的开头都是一个轻儿子 
	}
} 

void pushup(int u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u){
	auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
	if(root.add){
		left.add+=root.add,left.sum+=root.add*(left.r-left.l+1);
		right.add+=root.add,right.sum+=root.add*(right.r-right.l+1);
		root.add=0;
	}
}

void build(int u,int l,int r){
	tr[u]={l,r,0,nw[r]};
	if(l==r) return ;
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
} 

void update(int u,int l,int r,int k){
	if(l<=tr[u].l&&r>=tr[u].r){
		tr[u].add+=k;
		tr[u].sum+=k*(tr[u].r-tr[u].l+1);
		return ;
	}
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) update(u<<1,l,r,k);
	if(r>mid) update(u<<1|1,l,r,k);
	pushup(u);
}

int query(int u,int l,int r){
	if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum;
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	int res=0;
	if(l<=mid) res+=query(u<<1,l,r);
	if(r>mid) res+=query(u<<1|1,l,r);
	return res;
}

void update_path(int u,int v,int k){//更新一条路径
	while(top[u]!=top[v]){//类似于lca,先不断处理较低点的重链,直到二者重合
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		update(1,id[top[u]],id[u],k);
		u=fa[top[u]];
	}
	
	if(dep[u]<dep[v]) swap(u,v);
	update(1,id[v],id[u],k);
}

int query_path(int u,int v){//查询一条路径 
	int res=0;
	while(top[u]!=top[v]){//类似于lca,先不断处理较低点的重链,直到二者重合
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		res+=query(1,id[top[u]],id[u]);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]) swap(u,v);
	res+=query(1,id[v],id[u]);
	return res;
}

void update_tree(int u,int k){//更新一个子树的区间和
	update(1,id[u],id[u]+sz[u]-1,k);
}

int query_tree(int u){//查询一颗子树的区间和
	return query(1,id[u],id[u]+sz[u]-1);
}

void slove() {
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs1(1,0);//预处理出重儿子
	dfs2(1,1);//求一下dfs序 
	build(1,1,n);
// 	cout<<query(1,5,5)<<endl;
	cin>>m;
	while(m--){
		int t,u,v,k;
		cin>>t>>u;
		if(t==1){
			cin>>v>>k;
			update_path(u,v,k);
		}
		else if(t==2){
			cin>>k;
			update_tree(u,k);
		}
		else if(t==3){
			cin>>v;
			cout<<query_path(u,v)<<endl;
		}
		else {
			cout<<query_tree(u)<<endl;
		}
	}
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--) slove();
}