XX学校XX学校计算机机房倒闭了

王八蛋王八蛋XX老师不调代码不调代码

带着他的笔记本跑了

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=400005;
int n,m,ss,mod;
int num[N];
int dfn[N],rev[N],sz[N],top[N],dep[N],faa[N];
vector<int>mp[N];
struct node{
	int le;
	int ri;
	int sum;
	int lz;
}tree[N*4];
void pushup(int rt){
	tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;
	tree[rt].sum%=mod;
}
void pushdown(int rt){
	if(tree[rt].lz!=0){
		tree[rt*2].lz+=tree[rt].lz;
		tree[rt*2+1].lz+=tree[rt].lz;
		tree[rt*2].lz%=mod;
		tree[rt*2+1].lz%=mod;
		
		int mid=(tree[rt].le+tree[rt].ri)/2;
        tree[rt*2].sum+=tree[rt].lz*(mid-tree[rt*2].le+1);//左右分别求和加起来
        tree[rt*2+1].sum+=tree[rt].lz*(tree[rt*2+1].ri-mid);
        tree[rt*2].sum%=mod;
        tree[rt*2+1].sum%=mod;
		tree[rt].lz=0;
	}
}
void build(int rt,int l,int r){
	tree[rt].le=l;
	tree[rt].ri=r;
	tree[rt].lz=0;
	int mid=(l+r)/2;
	if(l==r){
		tree[rt].sum=num[rev[l]]; 
		return ;
	}
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	pushup(rt);
	
}
void updata(int rt,int cl,int cr,int val){
	if(tree[rt].le>=cl&&tree[rt].ri<=cr){
		tree[rt].sum+=(tree[rt].ri-tree[rt].ri+1)*val;
		tree[rt].sum%=mod;
		tree[rt].lz+=val;
		return;
	}
	pushdown(rt);
	if(tree[rt*2].ri>=cl)
		updata(rt*2,cl,cr,val);
	if(tree[rt*2+1].le<=cr)
		updata(rt*2+1,cl,cr,val);
	pushup(rt);
}
int query(int rt,int l,int r){
    if(tree[rt].le>=l && tree[rt].ri<=r)
        return tree[rt].sum%mod;
    pushdown(rt);
    int s=0;
    if(tree[rt*2].ri>=l)  s+=query(rt*2,l,r);
    if(tree[rt*2+1].le<=r)  s+=query(rt*2+1,l,r);
    return s%mod;
}
//------------
int st=0;
void dfs1(int x,int fa){
	sz[x]=1;
	int ma=-1;
	faa[x]=fa;
	dep[x]=dep[fa]+1;
	for(int i=0;i<mp[x].size();i++){
		int to=mp[x][i];
		if(to==fa){
			continue;
		}
		dfs1(to,x);
		sz[x]+=sz[to];
		if(mp[x][0]==fa||ma<sz[to]){
			ma=sz[to];
			swap(mp[x][0],mp[x][i]);
		}
	}
}
void dfs2(int x,int fa,int ttop){
	st++;
	dfn[x]=st;
	rev[st]=x;
	top[x]=ttop;
	if(mp[x][0]==fa){//没有儿子 
		return;
	}
	dfs2(mp[x][0],x,ttop);
	for(int i=1;i<mp[x].size();i++){
		int to=mp[x][i];
		if(to==fa){
			continue;
		}
		dfs2(to,x,to);
	}
}
int qrange(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){//当两个点不在同一条链上 
		if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
		int res=query(1,dfn[top[x]],dfn[x]);//ans加上x点到x所在链顶端 这一段区间的点权和
		ans+=res;
		ans%=mod;//按题意取模 
		x=faa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
	}
	//直到两个点处于一条链上
	if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点
	int res=query(1,dfn[x],dfn[y]);//这时再加上此时两个点的区间和即可
	ans+=res;
	return ans%mod;
}
void qup(int x,int y,int z){
	while(top[x]!=top[y]){//当两个点不在同一条链上 
		if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
		updata(1,dfn[top[x]],dfn[x],z);//ans加上x点到x所在链顶端 这一段区间的点权和
		x=faa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
	}
	//直到两个点处于一条链上
	if(dep[x]>dep[y])swap(x,y);//把x点深度更浅的那个点
	updata(1,dfn[x],dfn[y],z);
}
int treerange(int x){
	return query(1,dfn[x],dfn[x]+sz[x]-1);
}
void treeup(int x,int z){
	updata(1,dfn[x],dfn[x]+sz[x]-1,z); 
}
signed main(){
	ios::sync_with_stdio(false);
	cin >> n >>m >> ss >> mod;
	for(int i=1;i<=n;i++){
		cin >> num[i];
		num[i]%=mod;
	}
	for(int i=1;i<=n-1;i++){
		int a,b;
		cin >> a >> b;
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	dep[ss]=1;
	dfs1(ss,0);
	dfs2(ss,ss,ss);
	build(1,1,n);
	while(m--){
		int op;
		cin >> op;
		if(op==1){
			int x,y,z;
			cin >> x >> y >> z;
			qup(x,y,z);
		}
		else if(op==2){
			int x,y;
			cin >> x >> y;
			cout<<qrange(x,y)<<endl;
		}
		else if(op==3){
			int x,z;
			cin >> x >> z;
			treeup(x,z);
		}
		else{
			int x;
			cin >> x;
			cout<<treerange(x)<<endl;
		}
	}
}