悬1关
by starback24 @ 2023-06-21 21:08:38
@[starback24](/user/487199) 你活珠子大跌来给你调题了！（bushi
就是bzd为什么有个蜜汁缩进（不好意思
```cpp
#include<iostream>
#define int long long
#define soon a[i].to
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int cnt,n,m,r,mod,head[1000100],top[1001000],fa[1001000];
int son[1001000],siz[1001000],dfn[1001000],dep[1001000],sum,x[1001000];
int dc=0;
struct xdt{
#define ls p<<1
#define rs p<<1|1
int d[1001000],b[1001000],a[1000100];
void pushup(int p){
d[p]=d[ls]+d[rs];
d[p]=d[p]%mod;
}
void build(int s,int t,int p){
if(s==t){
d[p]=a[s]%mod;
return;
}
int m=(s+t)>>1;
build(s,m,ls);
build(m+1,t,rs);
pushup(p);
}
void update(int l,int r,int c,int s,int t,int p){
// cout<<l<<" "<<r<<" "<<c<<" "<<s<<" "<<t<<" "<<p<<endl;
if(l<=s&&t<=r){
d[p]+=(t-s+1)*c%mod;
b[p]+=c%mod;
// cout<<1<<endl;
return;
}
int m=(t+s)>>1;
if(b[p]&&s!=t){
d[ls]+=b[p]*(m-s+1)%mod;
d[rs]+=b[p]*(t-m)%mod;
b[ls]+=b[p]%mod;
b[rs]+=b[p]%mod;
b[p]=0;
}
//cout<<1<<endl;
if(l<=m){
// printf("%lld %lld %lld %lld %lld %lld\n",l,r,c,s,m,ls);
update(l,r,c,s,m,ls);
}
if(m<r){
// printf("%lld %lld %lld %lld %lld %lld\n",l,r,c,m+1,t,rs);
update(l,r,c,m+1,t,rs);
}
pushup(p);
}
int getsum(int l,int r,int s,int t,int p){
if(l<=s&&t<=r){
return d[p]%mod;
}
int m=(s+t)>>1;
if(b[p]){
d[ls]+=b[p]*(m-s+1)%mod;
d[rs]+=b[p]*(t-m)%mod;
b[ls]+=b[p]%mod;
b[rs]+=b[p]%mod;
b[p]=0;
}
int sum=0;
if(l<=m){
sum=getsum(l,r,s,m,ls)%mod;
}
if(r>m){
sum+=getsum(l,r,m+1,t,rs)%mod;
}
return sum;
}
}tree;
struct node{
int nxt,to;
}a[1000100];
void add(int u,int v){
a[++cnt].nxt=head[u];
a[cnt].to=v;
head[u]=cnt;
}
void dfs1(int p,int f){
fa[p]=f;
son[p]=-1;
siz[p]=1;
for(int i=head[p];i;i=a[i].nxt){
if(soon!=f){
dep[soon]=dep[p]+1;
// fa[soon]=p;
dfs1(soon,p);
siz[p]+=siz[soon];
if(son[p]==-1||siz[soon]>siz[son[p]]){
son[p]=soon;
}
}
}
}
void dfs2(int p,int t){
top[p]=t;
dfn[p]=++sum;
tree.a[sum]=x[p];
//rnk[sum]=p;
if(son[p]==-1){
return;
}
dfs2(son[p],t);
for(int i=head[p];i;i=a[i].nxt){
if(soon!=son[p]&&soon!=fa[p]){
dfs2(soon,soon);
}
}
}
int treesum(int x,int y){
int ans=0;
while(top[x]!=top[y]){
// cout<<x<<" "<<y<<endl;
if(dep[top[x]]<dep[top[y]]){
swap(x,y);
}
//cout<<x<<" "<<y<<endl;
ans=(ans+tree.getsum(dfn[top[x]],dfn[x],1,n,1))%mod;
x=fa[top[x]];
//cout<<x<<" "<<top[x]<<" "<<fa[top[x]]<<endl;
}
if(dep[x]>dep[y]){
swap(x,y);
}
return ans=(ans+tree.getsum(dfn[x],dfn[y],1,n,1))%mod;
}
void treeadd(int x,int y,int v){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
swap(x,y);
}
tree.update(dfn[top[x]],dfn[x],v%mod,1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y]){
swap(x,y);
}
tree.update(dfn[x],dfn[y],v%mod,1,n,1);
}
void solve(){
cin>>n>>m>>r>>mod;
for(int i=1;i<=n;i++){
cin>>x[i];
}
for(int i=1,x,y;i<n;i++){
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs1(r,0),dfs2(r,r);
tree.build(1,n,1);
// cout<<son[1]<<endl;
for(int i=1,op,x,y,z;i<=m;i++){
cin>>op;
if(op==1){
cin>>x>>y>>z;
treeadd(x,y,z);
}
if(op==2){
cin>>x>>y;
cout<<treesum(x,y)%mod<<endl;
}
if(op==3){
cin>>x>>y;
//cout<<dfn[x]<<" "<<siz[x]<<endl;
tree.update(dfn[x],dfn[x]+siz[x]-1,y%mod,1,n,1);
}
if(op==4){
cin>>x;
cout<<tree.getsum(dfn[x],dfn[x]+siz[x]-1,1,n,1)%mod<<endl;
}
}
}
signed main(){
int t=(dc?read():1);
while(t--)
solve();
return 0;
}
```
by eggegg185 @ 2023-06-22 11:12:45
@[eggegg185](/user/676055) 谢谢龟孙
by starback24 @ 2023-06-22 11:25:10
@[eggegg185](/user/676055) 没有关给你了
by starback24 @ 2023-06-22 11:25:25
@[starback24](/user/487199) 好好好
by eggegg185 @ 2023-06-22 11:29:09