首页 笔记，OI

前置知识 1
前置知识 2
（一些促进理解图可以看一下别人的）

# 树剖：

前置基础：DFS 序， 树形 DP，线段树，链式前向星……

树链剖分 就是对一棵树分成几条链，把树形变为线性，减少处理难度
需要处理的问题：

  • 将树从 x 到 y 结点最短路径上所有节点的值都加上 z
  • 求树从 x 到 y 结点最短路径上所有节点的值之和
  • 将以 x 为根节点的子树内所有节点值都加上 z
  • 求以 x 为根节点的子树内所有节点值之和

# 概念：

  • 重儿子：对于每一个非叶子节点 (x)，在它的儿子 (y,z……) 中 以儿子 (y，z……) 为根的子树大小最大的节点 (y,z…… 中的一个) 为该节点的重儿子 (PS: 若每个儿子的子树大小相同那么随意让一个儿子为该节点的重儿子）
  • 轻儿子：对于每一个非叶子节点，它的儿子中 非重儿子 的剩下所有儿子即为轻儿子
  • 叶子节点没有重儿子也没有轻儿子（因为它没有儿子。。）
  • 重边：一个父亲连接他的重儿子的边称为重边 // 原写法：连接任意两个重儿子的边叫做重边
  • 轻边：剩下的即为轻边
  • 重链：相邻重边连起来的 连接一条重儿子 的链叫重链

对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为 1 的链

每一条重链以轻儿子为起点

Code：
#include<bitsdc++.h> 
using namespace std;
const long long MAXN = 1e5+5;
struct edge{
	long long nxt,to;
	edge(long long a1=0,long long a2=0){
		nxt=a1;
		to=a2;
	}
};
long long n,m,root,tot,cnt,MOD,lazy[4 * MAXN],w[MAXN],dep[MAXN],fa[MAXN],size[MAXN],son[MAXN],top[MAXN],id[MAXN],val[MAXN],head[MAXN],tree[4 * MAXN];
edge e[4 * MAXN];
void add_edge(long long from,long long to){// 链式前向星记录
	e[++tot] = edge(head[from],to);
	head[from] = tot;
}
// 两遍 dfs 
void dfs1(long long now,long long f){
	long long maxn=0;// 记重儿子
	fa[now] = f;// 标记父亲
	dep[now] = dep[f] + 1;// 记住该点的深度
	size[now] = 1;// 该点的子树大小，需要包括自己
	for(long long i=head[now]; i; i=e[i].nxt){// 遍历
		long long to = e[i].to;
		if(to == f)// 若为父亲则就 continue
			continue;
		dfs1(to,now);//dfs 儿子，方便后面算子树大小
		if(!maxn || size[maxn] < size[to])// 如果当时 maxn 没被赋值（有可能是第一个，也有可能该点只有一个儿子）
 // 如果现在这个儿子为节点的子树大小比原本标记的大那么就代替
			maxn = to;// 代替
		size[now] += size[to];// 加上儿子的子树大小
	}
	son[now] = maxn;// 存 now 这个点的重儿子
}
void dfs2(long long now,long long topf){//now 为当前节点，topf 为当前链的链顶 (链最顶端的节点)
	id[now] = ++cnt;// 给该点个编号
	val[cnt] = w[now];// 把原本的值赋值在新编号上
	top[now] = topf;//top [] 为该节点所在链的顶端位置
	if(!son[now])	return;// 如果没有重儿子（儿子) 那么就返回
	dfs2(son[now],topf);// 先处理重儿子再处理轻儿子
	for(long long i=head[now]; i ; i=e[i].nxt){// 遍历
		long long to = e[i].to;
		if(to == fa[now] || to == son[now])// 如果为父亲或者遍历到重儿子就 continue，重儿子我们是最先 dfs 的
			continue;
		dfs2(to,to);// 对轻儿子进行处理
	}
}
// 线段树： 
void update(long long k){// 合并
	tree[k] = tree[k<<1] + tree[k<<1|1];
	tree[k] %= MOD;
}
void spread_lazy(long long l,long long r,long long k){
	if(lazy[k]){
		long long mid = (l+r)>>1;
		lazy[k<<1] += lazy[k];lazy[k<<1|1] += lazy[k];
		tree[k<<1] += (mid-l+1) * lazy[k];tree[k<<1|1] += (r-mid) * lazy[k];
		tree[k<<1] %= MOD;tree[k<<1|1] %= MOD;
		lazy[k<<1]%=MOD;lazy[k<<1|1]%=MOD;lazy[k]=0;
	}// 不稍微压压行没灵魂
}
void build_tree(long long now_l,long long now_r,long long k){// 经典的建树环节
	if(now_l == now_r){
		tree[k] = val[now_l] % MOD;
		return;
	}
	long long mid = (now_l+now_r)>>1;
	build_tree(now_l,mid,k<<1);
	build_tree(mid+1,now_r,k<<1|1);
	update(k);// 待会讲解一下 update 环节
}
void add(long long now_l,long long now_r,long long k,long long l,long long r,long long q){// 区间加
	if(l <= now_l && r >= now_r){
		tree[k] += (now_r-now_l+1) * q;
		tree[k]%=MOD;
		lazy[k] += q;// 传递懒标记
		lazy[k]%=MOD;// 不要忘记取模
		return;
	}
	spread_lazy(now_l,now_r,k);// 读取懒标记
	long long mid = (now_l+now_r)>>1;
	if(l <= mid)	add(now_l,mid,k<<1,l,r,q);
	if(r > mid)		add(mid+1,now_r,k<<1|1,l,r,q);
	update(k);// 合并
}
long long query(long long now_l,long long now_r,long long k,long long l,long long r){// 区间查询 线段树
	if(l <= now_l && r>=now_r)
		return tree[k] % MOD;
	spread_lazy(now_l,now_r,k);
	long long mid = (now_l+now_r)>>1,ans=0;
	if(l <= mid) ans+=query(now_l,mid,k<<1,l,r);
	if(r > mid)	ans+=query(mid+1,now_r,k<<1|1,l,r);
	return ans % MOD;
}
long long Ask_Range(long long x,long long y){ // 区间查询 树剖 
	long long ans = 0;
	while(top[x] != top[y]){  // 不在同一条链上 
		if(dep[top[x]] < dep[top[y]])	swap(x,y);// 始终让 x 为深度大的
		ans += query(1,n,1,id[top[x]],id[x]);
		ans%=MOD;
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])
		swap(x,y);
	ans += query(1,n,1,id[x],id[y]);
	return ans % MOD;
}
long long Ask_Son(long long x){  // 查询该节点以及其的子树 
	return query(1,n,1,id[x],id[x]+size[x]-1);  // 编号是连续的，so 起始位置是 x 终止位置是 id [x]+size [x]-1，把 x 减去 
}
void Update_Range(long long x,long long y,long long z){  // 区间修改  可能 dfs 序不连续
	while(top[x] != top[y]){  // 不在同一条链上 
		if(dep[top[x]] < dep[top[y]]){
        swap(x,y);
       } 
//		ans += query(1,n,1,id[top[x]],id[x]);
		add(1,n,1,id[top[x]],id[x],z);
//		ans%=mod;
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])
		swap(x,y);
//	ans += query(1,n,1,id[x],id[y]);
	add(1,n,1,id[x],id[y],z);
}
void Update_Son(long long x,long long z){  // 修改该节点以及其的子树 
	add(1,n,1,id[x],id[x] + size[x] - 1,z);// 同一棵子树的 dfs 序是连续的，深度小的 dfs 序小就在前边
}
int main(){
	scanf("%lld%lld%lld%lld",&n,&m,&root,&MOD);
	for(long long i=1; i<=n; i++){
//		cin>>w[i];
		scanf("%lld",&w[i]);
	}
	for(long long i=1; i<n; i++){
		long long from,to;
//		cin>>from>>to;
		scanf("%lld%lld",&from,&to);
		add_edge(from,to);
		add_edge(to,from);
	}
	dfs1(root,0);
	dfs2(root,0);
	build_tree(1,n,1);
	for(long long i=1; i<=m; i++){
		long long op,x,y,z;
		cin>>op;
		if(op==1){// 剩下的就是题目要求的
        cin>>x>>y>>z;
			Update_Range(x,y,z);
		}
		else if(op == 2){
			cin>>x>>y;
			printf("%lld\n",Ask_Range(x,y));
		}
		else if(op == 3){
			cin>>x>>z;
			Update_Son(x,z);
		}
		else if(op == 4){
			cin>>x;
			printf("%lld\n",Ask_Son(x));
		}
	}
	return 0;
}