Tree chain partition board

I learned it in this blog ： Detailed explanation of tree chain partition - Since he was a pawn in the wind and moon - Blog Garden

  What is tree chain dissection ？ In my shallow understanding , A tree is a tree structure ; The chain type is a linear structure . For linear structures , We have a big killer ： Line segment tree . And obviously , Segment trees cannot be directly used in tree structures .

So we thought , Can you cut the tree into multiple chains , Then put it together , Become a linear structure ？

We cut a tree several times , Become multiple “ heavy chain ”, Put it together again , Renumber , Insert the segment tree . This is tree chain dissection .

Luoguban sub problem ：【 Templates 】 Heavy chain subdivision / The tree chain splits - Luogu

Code ：

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
#define ls o<<1
#define rs o<<1|1
const int N = 1e5+5;
int n,m,root,mod;
int deep[N]; // Node depth 
int fa[N]; // Node father 
int son[N]; // The knot weighs son 
int tot[N]; // Node tree size 
vector<int> g[N]; // chart ,g[i] Record i All the sons of 
int idx[N], cnt=0; // Renumber the array 
int top[N]; //top[i] Express i The head node of the heavy chain 
int a[N];   //a[i] After the number i The weight of node number 
int b[N];   //b[i] Express i A weight 

int t[N<<2],lz[N<<2]; // Segment trees and lazy markers 

/*  First step 
 As we said above , First of all, we should treat the whole tree dfs Again , Find the heavy son of each node 
 By the way, deal with the depth of each node , And their father nodes 
*/
int dfs1(int u,int f,int dep){
	deep[u] = dep;
	fa[u] = f;
	tot[u] = 1;
	int sonsz = -1; // The size of a son's subtree 
	for(int v:g[u]){
		if(v==f) continue; // Skip father 
		tot[u] += dfs1(v,u,dep+1); //dfs Ergodic son 
		if(tot[v] > sonsz) sonsz = tot[v], son[u] = v;
	}
	return tot[u];
}
/*  The second step 
 The whole tree needs to be renumbered ,
 I put the weight of each node at the beginning b In array 
*/
void dfs2(int u,int topf){
	idx[u] = ++cnt; // New numbered node 
	a[cnt]=b[u]; // Record the weight of the new number 
	top[u] = topf;
	if(!son[u]) return; // It's over without a son 
	dfs2(son[u],topf); // If you have a son , continue dfs Running heavy chain 
	for(int v:g[u]){
		if(!idx[v]) dfs2(v,v); // To other sons , Open a new heavy chain dfs
	}
}
/*  The third step 
 According to the newly numbered tree , Project each point on the tree onto the segment tree 
*/
inline void pushup(int o){t[o] = (t[ls]+t[rs]+mod)%mod;}
inline void pushdn(int o, int l, int r){
	if(!lz[o]) return; // There is no lazy mark , end 
	int mid = l+r>>1;
	t[ls] = (t[ls]+lz[o]*(mid-l+1))%mod; //sum Value modification 
	t[rs] = (t[rs]+lz[o]*(r-mid))%mod;
	lz[ls] = (lz[ls]+lz[o])%mod;         //lz Value modification 
	lz[rs] = (lz[rs]+lz[o])%mod;
	lz[o] = 0;                           // At present lz Zero clearing 
}
void build(int o,int l,int r){
	if(l==r){t[o] = a[l]; return;}
	int mid = l+r>>1;
	build(ls,l,mid); build(rs,mid+1,r);
	pushup(o);
}
void upd(int o,int l,int r,int x,int y,int val){
	if(x<=l && r<=y){
		t[o] += val*(r-l+1);
		lz[o] += val;
		return;
	}
	pushdn(o,l,r);
	int mid = l+r>>1;
	if(x<=mid) upd(ls,l,mid,x,y,val);
	if(y >mid) upd(rs,mid+1,r,x,y,val);
	pushup(o);
}
int query(int o,int l,int r,int x,int y){
	int res = 0;
	if(x<=l && r<=y) return t[o];
	pushdn(o,l,r);
	int mid = l+r>>1;
	if(x<=mid) res = (res+query(ls,l,mid,x,y))%mod;
	if(y >mid) res = (res+query(rs,mid+1,r,x,y))%mod;
	return res;
}
/*  Step four 
 Write four operations 
*/
void treeAdd(int x,int y,int val){ //x,y Add... To your path val A weight 
	while(top[x]!=top[y]){ // When not on the same chain , Just keep jumping 
		if(deep[top[x]] < deep[top[y]]) swap(x,y); // Let the deep jump up 
		upd(1,1,n,idx[top[x]],idx[x], val); // Deal with the part of this heavy chain 
		x = fa[top[x]]; // Jump to the top of the chain fa It's about 
	}
	if(deep[x] > deep[y]) swap(x,y);
	upd(1,1,n,idx[x],idx[y],val);
}
int treeSum(int x,int y){
	int res = 0;
	while(top[x]!=top[y]){ // When not on the same chain , Just keep jumping 
		if(deep[top[x]] < deep[top[y]]) swap(x,y); // Let the deep jump up 
		res = (res+query(1,1,n,idx[top[x]],idx[x]))%mod; // Deal with the part of this heavy chain 
		x = fa[top[x]]; // Jump to the top of the chain fa It's about 
	}
	if(deep[x] > deep[y]) swap(x,y);
	res = (res+query(1,1,n,idx[x],idx[y]))%mod;
	return res;
}


signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin>>n>>m>>root>>mod;
	FOR(i,1,n) cin>>b[i];
	FOR(i,1,n-1){
		int u,v; cin>>u>>v;
		g[u].push_back(v); g[v].push_back(u);
	}
	dfs1(root,0,1);
	dfs2(root,root);
	build(1,1,n);
	while(m--){
		int op,x,y,z; cin>>op;
		if(op==1){
			cin>>x>>y>>z; z%=mod;
			treeAdd(x,y,z);
		}
		else if(op==2){
			cin>>x>>y;
			cout<<treeSum(x,y)<<'\n';
		}
		else if(op==3){
			cin>>x>>z; z%=mod;
			upd(1,1,n,idx[x],idx[x]+tot[x]-1,z);
		}
		else if(op==4){
			cin>>x;
			cout<<query(1,1,n,idx[x],idx[x]+tot[x]-1)<<'\n';
		}
	}
}