问题标题: 树链剖分补充-赶紧结帖

之前不是发了一个树剖模板吗

那个代码是**的啦

下面这个才是正解：

话说我写这个代码出现了n个小**误

1：线段树没加build()

2：初始化dfs1(),dfs2()都没写

3：线段树打成了单点修改

4：线段树的if(l>y||r<x)return 给我达成了if(x>y||r<x)return ；

5：没加%p

6：query(1,1,seg[0],seg[tx],seg[x]);写成了query(1,1,seg[0],tx,x);

7：query根本跟ans没关系结果我输出个ans（p==4）

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

童靴们一定要注意小**误呀doge

#include<bits/stdc++.h>
using namespace std;
struct node{int to,next;};node bian[200010];
int n,m,r,p,q,w,ans,cnt,a[100010],head[200010],tree[100010*4],lazy[100010*4];
int fath[100010],dep[100010],size[100010],son[100010];
int top[100010],seg[100010],rev[100010];
void add(int x,int y){
	cnt++;
	bian[cnt].to=y;
	bian[cnt].next=head[x];
	head[x]=cnt;
}
void build(int k,int l,int r){
	if(l==r){
		tree[k]=a[rev[l]];
		return ;
	}
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	tree[k]=tree[k*2]+tree[k*2+1]; 
}
void addp(int k,int l,int r,int v){//修改辅助 
	lazy[k]+=v%p;
	tree[k]+=(r-l+1)*v%p;
}
void down(int k,int l,int r){
	int mid=(l+r)/2;
	addp(k*2,l,mid,lazy[k]);
	addp(k*2+1,mid+1,r,lazy[k]);
	lazy[k]=0; 
}
void change(int k,int l,int r,int x,int y,int z){
	if(l>y||r<x)return ;
	if(l>=x&&r<=y)return addp(k,l,r,z);
	if(lazy[k])down(k,l,r);
	int mid=(l+r)/2;
	change(k*2,l,mid,x,y,z);
	change(k*2+1,mid+1,r,x,y,z);
	tree[k]=((tree[k*2]%p)+(tree[k*2+1]%p))%p;
}
int query(int k,int l,int r,int x,int y){
	if(l>y||r<x)return 0;
	if(l>=x&&r<=y)return tree[k]%p;
	if(lazy[k])down(k,l,r);
	int mid=(l+r)/2;
	return (query(k*2,l,mid,x,y))%p+(query(k*2+1,mid+1,r,x,y))%p;
}
void dfs1(int r,int x){
	fath[x]=r;
	dep[x]=dep[r]+1;
	size[x]=1;
	for(int k=head[x];k;k=bian[k].next){
		if(bian[k].to!=r){
			dfs1(x,bian[k].to);
			size[x]+=size[bian[k].to];
			if(size[bian[k].to]>size[son[x]])son[x]=bian[k].to;
		} 
	}
}
void dfs2(int x){
	if(son[x]){
		top[son[x]]=top[x];
		seg[son[x]]=++seg[0];
		rev[seg[son[x]]]=son[x];
		dfs2(son[x]);
	}
	for(int k=head[x];k;k=bian[k].next){
		if(!top[bian[k].to]){
			top[bian[k].to]=bian[k].to;
			seg[bian[k].to]=++seg[0];
			rev[seg[bian[k].to]]=bian[k].to;
			dfs2(bian[k].to); 
		}
	}
}
void check(int x,int y){//树上两点之间修改查询 
	int tx=top[x],ty=top[y];
	while(tx!=ty){
		if(dep[tx]<dep[ty])swap(x,y),swap(tx,ty);
		if(q==1)change(1,1,seg[0],seg[tx],seg[x],w);//操作1修改
		if(q==2)ans+=query(1,1,seg[0],seg[tx],seg[x]);//操作2查询 
		x=fath[tx],tx=top[x];
	}
	if(dep[x]>dep[y])swap(x,y);
	if(q==1)change(1,1,seg[0],seg[x],seg[y],w);//操作1修改
	if(q==2)ans+=query(1,1,seg[0],seg[x],seg[y]);//操作2查询 
}
int main(){
	cin>>n>>m>>r>>p;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n-1;i++){
		int x,y;cin>>x>>y;
		add(x,y);add(y,x);
	}
	dfs1(0,r);
	top[r]=r;seg[r]=++seg[0];rev[1]=r;
	dfs2(r); 
	build(1,1,seg[0]);	
	for(int i=1;i<=m;i++){
		int x,y;cin>>q;
		if(q==1){
			cin>>x>>y>>w;
			check(x,y);	
		}
		if(q==2){
			cin>>x>>y;ans=0;
			check(x,y);
			cout<<ans%p<<endl;
		}
		if(q==3){
			cin>>x>>w;
			change(1,1,seg[0],seg[x],seg[x]+size[x]-1,w);
		}
		if(q==4){
			cin>>x;ans=0;
			cout<<query(1,1,seg[0],seg[x],seg[x]+size[x]-1)%p<<endl;
		}
	}
	return 0;
} 

许金夫在2022-06-03 09:51:05追加了内容

又又又又又又又又要开新坑，赶紧结帖

许金夫在2022-06-03 10:56:11追加了内容

快快快