@[上杉越](/user/490826) build函数问题，要记录dfs序的逆操作rk，建树用rkx
by AAA404 @ 2023-08-12 19:53:22
按你代码里的操作也应该在建树时用w数组
by AAA404 @ 2023-08-12 19:54:42
而不是wt数组
by AAA404 @ 2023-08-12 19:55:58
@[AAA404](/user/723198) 谢谢义父，但28
by 上杉越 @ 2023-08-12 19:59:38
@[AAA404](/user/723198)
```cpp
#include<bits/stdc++.h>
#define N 200086
#define mid ((l+r)>>1)
using namespace std;
int head[N],to[N*2],nex[N*2],tot;
int top[N],id[N],cnt,w[N];
int n,m,r,p;
void add(int u,int v){
to[++tot]=v;
nex[tot]=head[u];
head[u]=tot;
}
int a[N],lazy[N],wt[N];
void build(int x,int l,int r){
if(l==r){
a[x]=w[l];
if(a[x]>p)a[x]%=p;
return ;
}
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
a[x]=(a[x<<1]+a[x<<1|1])%p;
}
void pushdown(int x,int len){
lazy[x<<1]+=lazy[x];
lazy[x<<1|1]+=lazy[x];
a[x<<1]+=lazy[x]*(len-(len>>1));
a[x<<1]%=p;
a[x<<1|1]+=lazy[x]*(len>>1);
a[x<<1|1]%=p;
lazy[x]=0;
}
int res;
void query(int x,int l,int r,int L,int R){
if(L<=l&&R>=r){
res+=a[x];
res%=p;
return;
}
else{
if(lazy[x])pushdown(x,r-l+1);
if(L<=mid)query(x<<1,l,mid,L,R);
if(R>mid)query(x<<1|1,mid+1,r,L,R);
}
}
void update(int x,int k,int l,int r,int L,int R){
if(L<=l&&R>=r){
lazy[x]+=k;
a[x]+=k*(r-l+1);
}
else{
if(lazy[x])pushdown(x,r-l+1);
if(L<=mid)update(x<<1,k,l,mid,L,R);
if(R>mid)update(x<<1|1,k,mid+1,r,L,R);
a[x]=(a[x<<1]+a[x<<1|1])%p;
}
}
int dep[N],fa[N],sonsize[N],son[N];
void dfs1(int x,int f,int deep){
fa[x]=f;
dep[x]=deep;
sonsize[x]=1;
int maxson=-1;
for(int i=head[x];i;i=nex[i]){
if(to[i]==f)continue;
dfs1(to[i],x,deep+1);
sonsize[x]+=sonsize[to[i]];
if(maxson<sonsize[to[i]]){
maxson=sonsize[to[i]];
son[x]=to[i];
}
}
}
void dfs2(int x,int topf){
id[x]=++cnt;
top[cnt]=topf;
w[cnt]=wt[x];
if(!son[x])return ;
dfs2(son[x],topf);
for(int i=head[x];i;i=nex[i]){
if(to[i]==son[x]||to[i]==fa[x])continue;
dfs2(to[i],to[i]);
}
}
int qSon(int x){
res=0;
query(1,1,n,id[x],id[x]+sonsize[x]-1);
return res;
}
void rSon(int x,int k){
update(1,k,1,n,id[x],id[x]+sonsize[x]-1);
}
int range(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
res=0;
query(1,1,n,id[top[x]],id[x]);
ans+=res;
ans%=p;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
res=0;
query(1,1,n,id[x],id[y]);
ans+=res;
ans%=p;
return ans;
}
void up_date(int x,int y,int k){
k%=p;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,k,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,k,1,n,id[x],id[y]);
}
int main(){
cin>>n>>m>>r>>p;
int x,y,z,B;
for(int i=1;i<=n;i++)cin>>wt[i];
for(int i=1;i<n;i++){
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,1,n);
for(int i=1;i<=m;i++){
cin>>B;
if(B==1){
cin>>x>>y>>z;
up_date(x,y,z);
}
if(B==2){
cin>>x>>y;
cout<<range(x,y)<<"\n";
}
if(B==3){
cin>>x>>y;
rSon(x,y);
}
if(B==4){
cin>>x;
cout<<qSon(x)<<"\n";
}
}
return 0;
}
```
by 上杉越 @ 2023-08-12 20:00:57
@[上杉越](/user/490826) az，代码发出来，我没写这题看不了
by AAA404 @ 2023-08-12 20:01:27
dfs2里的top不是cnt是x
by AAA404 @ 2023-08-12 20:02:50
@[AAA404](/user/723198)
谢谢大佬，73了
by 上杉越 @ 2023-08-12 20:04:18
@[AAA404](/user/723198)
```cpp
#include<bits/stdc++.h>
#define N 200086
#define mid ((l+r)>>1)
using namespace std;
int head[N],to[N*2],nex[N*2],tot;
int top[N],id[N],cnt,w[N];
int n,m,r,p;
void add(int u,int v){
to[++tot]=v;
nex[tot]=head[u];
head[u]=tot;
}
int a[N],lazy[N],wt[N];
void build(int x,int l,int r){
if(l==r){
a[x]=w[l];
if(a[x]>p)a[x]%=p;
return ;
}
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
a[x]=(a[x<<1]+a[x<<1|1])%p;
}
void pushdown(int x,int len){
lazy[x<<1]+=lazy[x];
lazy[x<<1|1]+=lazy[x];
a[x<<1]+=lazy[x]*(len-(len>>1));
a[x<<1]%=p;
a[x<<1|1]+=lazy[x]*(len>>1);
a[x<<1|1]%=p;
lazy[x]=0;
}
int res;
void query(int x,int l,int r,int L,int R){
if(L<=l&&R>=r){
res+=a[x];
res%=p;
return;
}
else{
if(lazy[x])pushdown(x,r-l+1);
if(L<=mid)query(x<<1,l,mid,L,R);
if(R>mid)query(x<<1|1,mid+1,r,L,R);
}
}
void update(int x,int k,int l,int r,int L,int R){
if(L<=l&&R>=r){
lazy[x]+=k;
a[x]+=k*(r-l+1);
}
else{
if(lazy[x])pushdown(x,r-l+1);
if(L<=mid)update(x<<1,k,l,mid,L,R);
if(R>mid)update(x<<1|1,k,mid+1,r,L,R);
a[x]=(a[x<<1]+a[x<<1|1])%p;
}
}
int dep[N],fa[N],sonsize[N],son[N];
void dfs1(int x,int f,int deep){
fa[x]=f;
dep[x]=deep;
sonsize[x]=1;
int maxson=-1;
for(int i=head[x];i;i=nex[i]){
if(to[i]==f)continue;
dfs1(to[i],x,deep+1);
sonsize[x]+=sonsize[to[i]];
if(maxson<sonsize[to[i]]){
maxson=sonsize[to[i]];
son[x]=to[i];
}
}
}
void dfs2(int x,int topf){
id[x]=++cnt;
top[x]=topf;
w[cnt]=wt[x];
if(!son[x])return ;
dfs2(son[x],topf);
for(int i=head[x];i;i=nex[i]){
if(to[i]==son[x]||to[i]==fa[x])continue;
dfs2(to[i],to[i]);
}
}
int qSon(int x){
res=0;
query(1,1,n,id[x],id[x]+sonsize[x]-1);
return res;
}
void rSon(int x,int k){
update(1,k,1,n,id[x],id[x]+sonsize[x]-1);
}
int range(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
res=0;
query(1,1,n,id[top[x]],id[x]);
ans+=res;
ans%=p;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
res=0;
query(1,1,n,id[x],id[y]);
ans+=res;
ans%=p;
return ans;
}
void up_date(int x,int y,int k){
k%=p;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,k,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,k,1,n,id[x],id[y]);
}
int main(){
cin>>n>>m>>r>>p;
int x,y,z,B;
for(int i=1;i<=n;i++)cin>>wt[i];
for(int i=1;i<n;i++){
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,1,n);
for(int i=1;i<=m;i++){
cin>>B;
if(B==1){
cin>>x>>y>>z;
up_date(x,y,z);
}
if(B==2){
cin>>x>>y;
cout<<range(x,y)<<"\n";
}
if(B==3){
cin>>x>>y;
rSon(x,y);
}
if(B==4){
cin>>x;
cout<<qSon(x)<<"\n";
}
}
return 0;
}
```
by 上杉越 @ 2023-08-12 20:04:53