@[Remedios](/user/1025802) 忘记去摸了捏
by XHY20180718 @ 2023-07-16 23:37:46
@[Remedios](/user/1025802)
多多取模，一般题不会卡这样的常。。。
```cpp
#include<stdio.h>
#include<ctype.h>
#include<vector>
using namespace std;
const long long N=1e5+10,SN=4e5+10;
long long mo;
long long read(){
long long res=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) res=(res<<3)+(res<<1)+c-48,c=getchar();
return res*f;
}
struct ST{
long long st[SN],lzm[SN];
long long ls(long long p){ return p<<1; }
long long rs(long long p){ return p<<1|1; }
long long mid(long long s,long long t){ return s+((t-s)>>1); }
void pushup(long long p){
st[p]=st[ls(p)]+st[rs(p)];
st[p]%=mo;
}
void add(long long s,long long t,long long p,long long k){
st[p]+=(t-s+1)*k,lzm[p]+=k;
st[p]%=mo,lzm[p]%=mo;
}
void pushdown(long long s,long long t,long long p){
long long m=mid(s,t);
add(s,m,ls(p),lzm[p]),add(m+1,t,rs(p),lzm[p]);
lzm[p]=0;
}
void build(long long s,long long t,long long p,long long *od){
if(s==t){
st[p]=od[s]%mo;
return ;
}
long long m=mid(s,t);
build(s,m,ls(p),od),build(m+1,t,rs(p),od);
pushup(p);
}
void sec_add(long long l,long long r,long long s,long long t,long long p,long long k){
if(s>=l&&t<=r){
add(s,t,p,k);
return ;
}
long long m=mid(s,t); pushdown(s,t,p);
if(m>=l) sec_add(l,r,s,m,ls(p),k);
if(m<r) sec_add(l,r,m+1,t,rs(p),k);
pushup(p);
}
long long sec_query(long long l,long long r,long long s,long long t,long long p){
if(s>=l&&t<=r) return st[p];
long long m=mid(s,t),sum=0; pushdown(s,t,p);
if(m>=l) sum+=sec_query(l,r,s,m,ls(p)),sum%=mo;
if(m<r) sum+=sec_query(l,r,m+1,t,rs(p)),sum%=mo;
return sum;
}
};
struct node{
long long vl,fa,dep,size,hs,top,dfn,bot;
node(){}
};
struct HD{
long long n,rt,rnk[N],tot,df[N];
node nd[N];
vector<vector<long long>> g;
ST da;
long long tree_build(long long p,long long dep){
nd[p].dep=dep,nd[p].size=1;
for(auto i:g[p])if(!nd[i].dep){
nd[p].size+=tree_build(i,dep+1);
nd[i].fa=p;
if(nd[i].size>nd[nd[p].hs].size) nd[p].hs=i;
}
return nd[p].size;
}
long long tree_decomposition(long long p,long long top){
nd[p].dfn=++tot,rnk[tot]=p,nd[p].top=top,df[tot]=nd[p].vl,nd[p].bot=p;
if(nd[p].hs) nd[p].bot=nd[tree_decomposition(nd[p].hs,top)].dfn>nd[nd[p].bot].dfn?nd[nd[p].hs].bot:nd[p].bot;
for(auto i:g[p]) if(!nd[i].dfn) nd[p].bot=nd[tree_decomposition(i,i)].dfn>nd[nd[p].bot].dfn?nd[i].bot:nd[p].bot;
return nd[p].bot;
}
//HD(){}
//HD(long long n1,long long r1,long long *od):n(n1),rt(r1){
void build(long long n1,long long r1,long long *od){
n=n1,rt=r1;
g.resize(n+1);
for(long long i=1;i<=n;i++) nd[i].vl=od[i];
for(long long i=1;i<n;i++){
long long u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
tree_build(rt,1); tree_decomposition(rt,rt);
da.build(1,n,1,df);
}
void path_add(long long s,long long t,long long k){
while(nd[s].top!=nd[t].top){
if(nd[nd[s].top].dep<nd[nd[t].top].dep) swap(s,t);
da.sec_add(nd[nd[s].top].dfn,nd[s].dfn,1,n,1,k);
s=nd[nd[s].top].fa;
}
long long ms=min(nd[s].dfn,nd[t].dfn),bs=nd[s].dfn+nd[t].dfn-ms;
da.sec_add(ms,bs,1,n,1,k);
}
void subtree_add(long long p,long long k){ da.sec_add(nd[p].dfn,nd[nd[p].bot].dfn,1,n,1,k); }
long long path_query(long long s,long long t){
long long sum=0;
while(nd[s].top!=nd[t].top){
if(nd[nd[s].top].dep<nd[nd[t].top].dep) swap(s,t);
(sum+=da.sec_query(nd[nd[s].top].dfn,nd[s].dfn,1,n,1))%=mo;
s=nd[nd[s].top].fa;
}
long long ms=min(nd[s].dfn,nd[t].dfn),bs=nd[s].dfn+nd[t].dfn-ms;
(sum+=da.sec_query(ms,bs,1,n,1))%=mo;
return sum;
}
long long subtree_query(long long p){ return da.sec_query(nd[p].dfn,nd[nd[p].bot].dfn,1,n,1); }
} hd;
long long arr[N];
int main(){
long long nn=read(),em=read(),ro=read(); mo=read();
for(long long i=1;i<=nn;i++) arr[i]=read();
hd.build(nn,ro,arr);
while(em--){
long long opt=read(),x,y,k;
switch(opt){
case 1:x=read(),y=read(),k=read(); hd.path_add(x,y,k);break;
case 2:x=read(),y=read(); printf("%lld\n",hd.path_query(x,y));break;
case 3:x=read(),k=read(); hd.subtree_add(x,k);break;
case 4:x=read(); printf("%lld\n",hd.subtree_query(x));break;
}
}
return 0;
}
```
能给个关注吗？
by XHY20180718 @ 2023-07-16 23:44:17
@[XHY20180718](/user/399475) 谢谢你捏
by Remedios @ 2023-07-16 23:46:00
@[XHY20180718](/user/399475) 灌注了捏，太谢谢了哥
by Remedios @ 2023-07-16 23:53:26