thousands_of_years @ 2024-07-10 15:56:56
哪里错了呀，万能的谷民们救救我！！！
#include<bits/stdc++.h>
#define N 100005
using namespace std;
long long a[8*N],lazy[8*N],n,m,x,y,k,h[8*N],w[8*N],fa[8*N],dep[8*N],siz[8*N],son[8*N],top[8*N],id[8*N],p;
int cnt;
struct Node{
int ne,to,val;
}e[8*N];
void addl(int u,int v)
{
e[++cnt].ne=h[u];
e[cnt].to=v;
h[u]=cnt;
}
void push_up(int num)
{
a[num]=a[num*2]+a[num*2+1];
}
void push_down(int num,int l,int r)
{
if(lazy[num])
{
lazy[num*2]+=lazy[num];
lazy[num*2+1]+=lazy[num];
int mid=(l+r)>>1;
a[num*2]+=(mid-l+1)*lazy[num];
a[num*2+1]+=(r-mid)*lazy[num];
lazy[num]=0;
}
}
void build(int l,int r,int num)
{
if(l==r)
{
w[l]%=p;
a[num]=w[l];
}
else
{
int mid=(l+r)>>1;
build(l,mid,2*num);
build(mid+1,r,2*num+1);
push_up(num);
}
}
void add(int x,int y,int k,int l,int r,int num)
{
if(x<=l&&y>=r)
{
lazy[num]+=k;
a[num]+=(r-l+1)*k;
}
else
{
push_down(num,l,r);
int mid=(l+r)>>1;
if(x<=mid) add(x,y,k,l,mid,num*2);
if(y>mid) add(x,y,k,mid+1,r,num*2+1);
push_up(num);
}
}
long long find(int x,int y,int l,int r,int num)
{
if(x<=l && y>=r) return a[num];
push_down(num,l,r);
{
int mid=(l+r)>>1;
long long ans=0;
if(x<=mid) ans+=find(x,y,l,mid,num*2);
if(y>mid) ans+=find(x,y,mid+1,r,num*2+1);
return ans;
}
}
void dfs1(int u,int f,int deep)
{
dep[u]=deep;
fa[u]=f;
siz[u]=1;
int maxson=-1;
for(int i=h[u];i;i=e[i].ne)
{
int v=e[i].to;
if(v==f) continue;
dfs1(v,u,deep+1);
siz[u]+=siz[v];
if(siz[v]>maxson)
{
son[u]=v;
maxson=siz[v];
}
}
}
void dfs2(int u,int tto)
{
id[u]=++cnt;
w[cnt]=w[u];
top[u]=tto;
if(!son[u])
return ;
dfs2(son[u],tto);
for(int i=h[u];i;i=e[i].ne)
{
int v=e[i].to;
if(v==fa[u]||v==son[u])
continue;
dfs2(v,v);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int r;
cin>>n>>m>>r>>p;
for(int i=1;i<=n;i++)
cin>>w[i];
for(int i=1;i<n;i++)
{
cin>>x>>y;
addl(x,y);
addl(y,x);
}
cnt=0;
dfs1(r,0,1);
dfs2(r,r);
build(1,n,1);
for(int i=1;i<=m;i++)
{
int opt;
cin>>opt;
if(opt==1)
{
cin>>x>>y>>k;
k%=p;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
add(id[top[x]],id[x],k,1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
add(id[x],id[y],k,1,n,1);
}
if(opt==2)
{
long long ans=0;
cin>>x>>y;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=find(id[top[x]],id[x],1,n,1);
ans%=p;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=find(id[x],id[y],1,n,1);
cout<<ans%p<<"\n";
}
if(opt==3)
{
cin>>x>>y;
add(id[x],id[x]+siz[x]-1,y,1,n,1);
}
if(opt==4)
{
cin>>x;
cout<<find(id[x],id[x]+siz[x]-1,1,n,1)<<"\n";
}
}
return 0;
} by o0_yuanshen_0o @ 2024-07-10 17:20:15
额。。。
by UncleSam_Died @ 2024-07-10 17:28:10
@The_last_one 帮你调出来了，你这个错误……额，惨不忍睹？就是说你在根据dfs序修改 w 数组的时候，你是直接用原来的数组修改的，但是你这样修改有一个问题，你可能在修改的过程中覆盖某些位置上的值，最后得到一个错误的 w 数组，你把这里改了就好了。
by UncleSam_Died @ 2024-07-10 17:28:29
@The_last_one 代码：
#include<bits/stdc++.h>
#define N 100005
using namespace std;
#define int long long
long long a[8*N],lazy[8*N],n,m,x,y,k,h[8*N],w[8*N],fa[8*N],dep[8*N],siz[8*N],son[8*N],top[8*N],id[8*N],p;
int cnt,wt[N<<3];
struct Node{
int ne,to,val;
}e[8*N];
void addl(int u,int v)
{
e[++cnt].ne=h[u];
e[cnt].to=v;
h[u]=cnt;
}
void push_up(int num)
{
a[num]=(a[num*2]+a[num*2+1])%p;
}
void push_down(int num,int l,int r)
{
if(lazy[num])
{
lazy[num*2]+=lazy[num];
lazy[num*2+1]+=lazy[num];
int len=r-l+1,len2=len/2;
a[num*2]+=lazy[num]*(len-len2)%p;
a[num*2+1]+=lazy[num]*len2%p;
lazy[num]=0; a[num*2]%=p,a[num*2+1]%=p;
}
}
void build(int l,int r,int num)
{
if(l==r)
{
a[num]=wt[l];
a[num]%=p;
return;
}
else
{
int mid=(l+r)>>1;
build(l,mid,2*num);
build(mid+1,r,2*num+1);
push_up(num);
}
}
void add(int x,int y,int k,int l,int r,int num)
{
if(x<=l&&y>=r)
{
lazy[num]+=k;
a[num]+=(r-l+1)*k;
a[num]%=p; lazy[num]%=p;
}
else
{
if(lazy[num]) push_down(num,l,r);
int mid=(l+r)>>1;
if(x<=mid) add(x,y,k,l,mid,num*2);
if(y>mid) add(x,y,k,mid+1,r,num*2+1);
push_up(num);
}
}
int res;
void find(int x,int y,int l,int r,int num)
{
if(x<=l && y>=r){
res+=a[num];
res%=p; return;
}
else {
push_down(num,l,r);
int mid=(l+r)>>1;
if(x<=mid) find(x,y,l,mid,num*2);
if(y>mid) find(x,y,mid+1,r,num*2+1);
}
}
void dfs1(int u,int f,int deep)
{
dep[u]=deep;
fa[u]=f;
siz[u]=1;
int maxson=-1;
for(int i=h[u];i;i=e[i].ne)
{
int v=e[i].to;
if(v==f) continue;
dfs1(v,u,deep+1);
siz[u]+=siz[v];
if(siz[v]>maxson)
{
son[u]=v;
maxson=siz[v];
}
}
}
int cntdfn;
void dfs2(int u,int tto)
{
id[u]=++cntdfn;
wt[cntdfn]=w[u];
top[u]=tto;
if(!son[u])
return ;
dfs2(son[u],tto);
for(int i=h[u];i;i=e[i].ne)
{
int v=e[i].to;
if(v==fa[u]||v==son[u])
continue; dfs2(v,v);
}
}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
int r; cin>>n>>m>>r>>p;
for(int i=1;i<=n;i++)
cin>>w[i];
for(int i=1;i<n;i++)
{
cin>>x>>y;
addl(x,y);
addl(y,x);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,n,1);
for(int i=1;i<=m;i++)
{
int opt;
cin>>opt;
if(opt==1)
{
cin>>x>>y>>k;
k%=p;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
add(id[top[x]],id[x],k,1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
add(id[x],id[y],k,1,n,1);
}
if(opt==2)
{
long long ans=0;
cin>>x>>y;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=0; find(id[top[x]],id[x],1,n,1);
ans+=res; ans%=p; x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res=0; find(id[x],id[y],1,n,1);
ans+=res; cout<<ans%p<<"\n";
}
if(opt==3)
{
cin>>x>>y;
add(id[x],id[x]+siz[x]-1,y,1,n,1);
}
if(opt==4)
{
cin>>x; res=0;
find(id[x],id[x]+siz[x]-1,1,n,1);
cout<<res<<"\n";
}
}
}
by UncleSam_Died @ 2024-07-10 17:28:48
@The_last_one 有用求关~
by thousands_of_years @ 2024-07-10 17:33:12
@UncleSam_Died 拜谢大佬
by thousands_of_years @ 2024-07-10 17:44:46
@UncleSam_Died
dalao， 你不会是在mz集训吧？ 不会是远志楼6楼？
by UncleSam_Died @ 2024-07-10 17:49:58
@The_last_one ？
by UncleSam_Died @ 2024-07-10 17:50:09
@The_last_one 你是？
by thousands_of_years @ 2024-07-10 17:51:27
隔壁
by thousands_of_years @ 2024-07-10 17:52:04
洛谷太小了