题面
https://www.luogu.org/problem/P3384
题解
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; struct node{ long long lb,rb,add,val; } tree[405000]; long long n,m,r,p,a[105000],dfsxu[105000],cnt,le[105000],re[105000],sum; long long d[105000],fa[105000],top[105000],siz[105000],fatson[105000]; vector <long long> to[105000]; void dfs1(long long x,long long da,long long deep){ long long i,l=to[x].size(),fs=-1,maxd=0; fa[x]=da; d[x]=deep; siz[x]=1; for (i=0;i<l;i++) if (to[x][i]!=da) { dfs1(to[x][i],x,deep+1); siz[x]+=siz[to[x][i]]; if (siz[to[x][i]]>maxd) maxd=siz[to[x][i]],fs=to[x][i]; } fatson[x]=fs; } void dfs2(long long x,bool is){ long long i,l=to[x].size(); dfsxu[++cnt]=x; le[x]=cnt; if (is) top[x]=top[fa[x]]; else top[x]=x; if (fatson[x]!=-1) dfs2(fatson[x],1); for (i=0;i<l;i++) if (to[x][i]!=fa[x] && to[x][i]!=fatson[x]) dfs2(to[x][i],0); re[x]=cnt; } void makesegmenttree(long long x,long long l,long long r){ tree[x].lb=l; tree[x].rb=r; if (l==r) { tree[x].val=a[dfsxu[l]]; return; } long long mid=(l+r)/2; makesegmenttree(2*x,l,mid); makesegmenttree(2*x+1,mid+1,r); tree[x].val=(tree[2*x].val+tree[2*x+1].val)%p; } void pushdown(long long x){ long long kk=tree[x].add; tree[x].add=0; tree[2*x].val+=(tree[2*x].rb-tree[2*x].lb+1)*kk; tree[2*x].val%=p; tree[2*x].add+=kk; tree[2*x].add%=p; tree[2*x+1].val+=(tree[2*x+1].rb-tree[2*x+1].lb+1)*kk; tree[2*x+1].val%=p; tree[2*x+1].add+=kk; tree[2*x+1].add%=p; } void cha(long long x,long long l,long long r){ if (l>tree[x].rb || r<tree[x].lb) return; if (l<=tree[x].lb && tree[x].rb<=r) { sum+=tree[x].val; sum%=p; return; } if (tree[x].add!=0) pushdown(x); cha(2*x,l,r); cha(2*x+1,l,r); } void jia(long long x,long long l,long long r,long long kk){ if (l>tree[x].rb || r<tree[x].lb) return; if (l<=tree[x].lb && tree[x].rb<=r) { tree[x].val+=kk*(tree[x].rb-tree[x].lb+1); tree[x].val%=p; tree[x].add+=kk; tree[x].add%=p; return; } if (tree[x].add!=0) pushdown(x); jia(2*x,l,r,kk); jia(2*x+1,l,r,kk); tree[x].val=(tree[2*x].val+tree[2*x+1].val)%p; } void jialian(long long u,long long v,long long kk){ while (top[u]!=top[v]) { if (d[top[u]]<d[top[v]]) swap(u,v); jia(1,le[top[u]],le[u],kk); u=fa[top[u]]; } if (d[u]<d[v]) swap(u,v); jia(1,le[v],le[u],kk); } void chalian(long long u,long long v){ while (top[u]!=top[v]) { if (d[top[u]]<d[top[v]]) swap(u,v); cha(1,le[top[u]],le[u]); u=fa[top[u]]; } if (d[u]<d[v]) swap(u,v); cha(1,le[v],le[u]); } int main() { //freopen("dd.cpp","r",stdin); long long i,u,v,opt,k; scanf("%lld %lld %lld %lld",&n,&m,&r,&p); for (i=1;i<=n;i++) { scanf("%lld",&a[i]); a[i]%=p; } for (i=1;i<n;i++) { scanf("%lld %lld",&u,&v); to[u].push_back(v); to[v].push_back(u); } cnt=0; dfs1(r,-1,1); dfs2(r,0); /* cout<<"ylq::"; for (i=1;i<=n;i++) cout<<dfsxu[i]<<" "; puts(""); for (i=1;i<=n;i++) cout<<"ylq"<<le[i]<<" "<<re[i]<<endl; */ makesegmenttree(1,1,n); for (i=1;i<=m;i++) { scanf("%lld",&opt); if (opt==4) { scanf("%lld",&u); sum=0; //printf("ylq::%lld %d ",le[u],re[u]); cha(1,le[u],re[u]); printf("%lld ",sum); } if (opt==3) { scanf("%lld %lld",&u,&k); //printf("ylq::%lld %lld %d ",le[u],re[u],k); jia(1,le[u],re[u],k); } if (opt==1) { scanf("%lld %lld %lld",&u,&v,&k); jialian(u,v,k); } if (opt==2) { scanf("%lld %lld",&u,&v); sum=0; chalian(u,v); printf("%lld ",sum); } } }