20分求助
查看原帖
20分求助
119638
xia0ji233楼主2021/4/1 16:46

照着标程写上去的,第二个点就是过不去,本地测试第二个点就是RE,不知道为什么,标程也是RE。求各位大佬指点一二

#include<iostream>
#define int long long
#define rint register int
#define mid (l+r>>1)
#define lson now<<1,l,mid
#define rson now<<1|1,mid+1,r
using namespace std;
const int maxn=1e5+200;
struct aaa{
	int next,v;
}edge[maxn<<1];
struct aa{
	int l,r,sum,lazy_tag;
}tree[maxn<<2];
int fa[maxn],id[maxn],v[maxn],w[maxn],dep[maxn],size[maxn],son[maxn],top[maxn],head[maxn],cnt,n,mod;
//top[i]表示i点所在重链的起点 
inline void add_edge(int,int);
inline void dfs1(int,int,int);
inline void dfs2(int,int);
inline void build(int,int,int);
inline void push_down(int);
inline void add(int,int,int,int);
inline void add(int,int);
inline void link_add(int,int,int);
inline int  query(int,int,int);
inline int  query(int);
inline int  link_query(int,int);
signed main(){
	freopen("in.txt","r",stdin);
	int m,root;
	cin>>n>>m>>root>>mod;
	for(rint i=1;i<=n;i++){
		cin>>v[i];
	}
	for(rint i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		add_edge(x,y);
		add_edge(y,x);
	}
	dfs1(root,0,1);
	cnt=0;
//	dfs2(root,root);
//	build(1,1,n);/*
	while(m--){
		int k,x,y,z;
		cin>>k;
		if(k==1){
			cin>>x>>y>>z;
			link_add(x,y,z);
		}
		else if(k==2){
			cin>>x>>y;
			cout<<link_query(x,y)%mod<<endl;
		}
		else if(k==3){
			cin>>x>>z;
			add(x,z);
		}
		else{
			cin>>x;
			cout<<query(x)%mod<<endl;
		}
	}
	//for(int i=1;i<=15;i++){
	//	cout<<tree[i].lazy_tag<<' ';
	//*/
	return 0;
}
inline void add_edge(int x,int y){
	edge[++cnt].next=head[x];
	edge[cnt].v=y;
	head[x]=cnt;
}
inline void dfs1(int now,int father,int depth){
	dep[now]=depth;
	fa[now]=father;
	size[now]=1;
	int heavier_son=-1;
	for(rint i=head[now];i;i=edge[i].next){
		int y=edge[i].v;
		if(y==father){
			//cout<<"aaa"<<endl;
			continue;
		}
		//cout<<y<<' '<<father<<endl;
		dfs1(y,now,depth+1);
		size[now]+=size[y];
		//cout<<size[now]<<endl;
		if(size[heavier_son]<size[y])heavier_son=y;
	}
	son[now]=heavier_son;
	//cout<<'1'<<endl;
}
inline void dfs2(int now,int topf){
	id[now]=++cnt;
	w[cnt]=v[now];
	top[now]=topf;
	if(!son[now])return;
	dfs2(son[now],topf);
	for(rint i=head[now];i;i=edge[i].next){
		int y=edge[i].v;
		if(y!=son[now]&&y!=fa[now])dfs2(y,y);
	}
}
inline void build(int now,int l,int r){
	tree[now].l=l,tree[now].r=r;
	if(l==r){
		tree[now].sum=w[l];
		return ;
	}
	build(lson);
	build(rson);
	tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
}
inline void push_down(int i){
	if(tree[i].lazy_tag){
		tree[i].sum+=(tree[i].r-tree[i].l+1)*tree[i].lazy_tag;
		if(tree[i].l!=tree[i].r){
			tree[i<<1].lazy_tag+=tree[i].lazy_tag;
			tree[i<<1|1].lazy_tag+=tree[i].lazy_tag;
			
		}
		tree[i].lazy_tag=0;
	}	
}
inline void add(int now,int l,int r,int num){
	if(tree[now].l>r||tree[now].r<l)return;
	if(tree[now].l>=l&&tree[now].r<=r){
		tree[now].lazy_tag+=num;
		return;
	}
	if(tree[now].l<=l&&tree[now].r>=r)tree[now].sum=(tree[now].sum+(r-l+1)*num)%mod;
	else if(l>=tree[now].l)tree[now].sum=(tree[now].sum+(tree[now].r-l+1)*num)%mod;
	else tree[now].sum+=(tree[now].sum+(r-tree[now].l+1)*num)%mod;
	add(now<<1,l,r,num);
	add(now<<1|1,l,r,num);
}
inline void add(int i,int num){
	add(1,id[i],id[i]+size[i]-1,num);
}
inline void link_add(int x,int y,int num){
	num%=mod;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		add(1,id[top[x]],id[x],num);
		x=fa[top[x]];
	}
	if(id[x]>id[y])swap(x,y);
	add(1,id[x],id[y],num);
}
inline int query(int now,int l,int r){
	
	if(tree[now].l>r||tree[now].r<l)return 0;
	push_down(now);
	if(tree[now].l>=l&&tree[now].r<=r)return tree[now].sum;
	return query(now<<1,l,r)+query(now<<1|1,l,r);

}
inline int query(int x){
	//cout<<id[x]<<' '<<id[x]+size[x]-1<<endl;
	return query(1,id[x],id[x]+size[x]-1);
}
inline int link_query(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		//cout<<id[top[x]]<<' '<<id[x]<<endl;
		ans+=query(1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(id[x]>id[y])swap(x,y);
	return ans+query(1,id[x],id[y]);
}
2021/4/1 16:46
加载中...