sorry,看不懂
by 已注销&M73*K7U @ 2019-07-10 19:59:04
@[迷失在黑夜里](/space/show?uid=201565) QAQ但是谢谢你点你进来看了鸭
by 澪lane @ 2019-07-10 20:12:50
```
%:pragma GCC optimize(2)
#include<bits/stdc++.h>
#define scf scanf
#define ptf printf
#define ll long long
#define Rint register int
#define mid (l+r>>1)
#define lson k<<1
#define rson k<<1|1
using namespace std;
const int N_=8e6+101;
int lazy[N_],sum[N_];
int Mod;
const int N=8e6+101;
int n,m,r_;
int cnt=0,tot=0,num,res=0;
int head[N],nex[N],to[N];
int w[N],w_[N],father[N],son[N],siz[N],id[N],deep[N],top[N];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')
f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void add(Rint u,Rint v){
to[++tot]=v;
nex[tot]=head[u];
head[u]=tot;
}
namespace segment_tree{
inline void build(Rint k,Rint l,Rint r){
if(l==r){
(sum[k]=w_[l])%=Mod;
return ;
}
build(lson,l,mid);
build(rson,mid+1,r);
sum[k]=(sum[lson]+sum[rson])%Mod;
}
inline void pushdown(Rint k,Rint len){
lazy[lson]+=lazy[k];
lazy[rson]+=lazy[k];
(sum[lson]+=lazy[k]*(len-(len>>1)))%=Mod;
(sum[rson]+=lazy[k]*(len>>1))%=Mod;
lazy[k]=0;
return ;
}
inline void update(Rint k,Rint l,Rint r,Rint L,Rint R,Rint x){
if(L<=l&&r<=R){
lazy[k]+=x;
sum[k]+=x*(r-l+1);
return ;
}
else{
if(lazy[k])
pushdown(k,r-l+1);
if(L<=mid)
update(lson,l,mid,L,R,x);
if(R>mid)
update(rson,mid+1,r,L,R,x);
sum[k]=(sum[lson]+sum[rson])%Mod;
}
}
inline void ask(Rint k,Rint l,Rint r,Rint L,Rint R){
if(L<=l&&r<=R){
(res+=sum[k])%=Mod;
// ptf("num=%d sum=%d\n",res,sum[k]);
return ;
}
else{
if(lazy[k])
pushdown(k,r-l+1);
if(L<=mid)
ask(lson,l,mid,L,R);
if(R>mid)
ask(rson,mid+1,r,L,R);
}
}
}
inline void up_road(Rint x,Rint y,Rint k){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])
swap(x,y);
segment_tree::update(1,1,n,id[top[x]],id[x],k);
x=father[top[x]];
//QAQ 您这写错了
}
if(deep[x]>deep[y])
swap(x,y);
segment_tree::update(1,1,n,id[x],id[y],k);
}
inline int qt_road(Rint x,Rint y){
int ans=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])
swap(x,y);
num=0,res=0;
segment_tree::ask(1,1,n,id[top[x]],id[x]);
(ans+=res)%=Mod;
x=father[top[x]];
}
if(deep[x]>deep[y])
swap(x,y);
res=0;segment_tree::ask(1,1,n,id[x],id[y]);
(ans+=res)%=Mod;
return ans;
}
inline void up_son(Rint x,Rint k){
segment_tree::update(1,1,n,id[x],id[x]+siz[x]-1,k);
}
inline int qt_son(Rint x){
res=0;
segment_tree::ask(1,1,n,id[x],id[x]+siz[x]-1);
return res;
}
inline void dfs_o(Rint x,Rint dad,Rint dep){
deep[x]=dep;
father[x]=dad;
siz[x]=1;
int max_son=-101;
for(Rint i=head[x];i!=-1;i=nex[i]){
int y=to[i];
if(y==dad)
continue;
dfs_o(y,x,dep+1);
siz[x]+=siz[y];
if(siz[y]>max_son)
son[x]=y,max_son=siz[y];
}
}
inline void dfs_p(Rint x,Rint rot){
id[x]=++cnt;
w_[cnt]=w[x];
top[x]=rot;
if(!son[x])
return ;
dfs_p(son[x],rot);
for(Rint i=head[x];i!=-1;i=nex[i]){
int y=to[i];
if(y==father[x]||y==son[x])
continue;
dfs_p(y,y);
}
}
int main(){
n=read(),m=read(),r_=read();
Mod=read();
memset(head,-1,sizeof head);
for(Rint i=1;i<=n;i++)
w[i]=read();
for(Rint i=1;i<n;i++){
int x=read(),y=read();
add(x,y),add(y,x);
}
dfs_o(r_,0,1);
dfs_p(r_,r_);
segment_tree::build(1,1,n);
for(int i=1;i<=m;i++){
int type=read();
int x,y,z;
if(type==1){
x=read(),y=read(),z=read();
up_road(x,y,z);
}
if(type==2){
x=read(),y=read();
ptf("%d\n",qt_road(x,y));
}
if(type==3){
x=read(),z=read();
up_son(x,z);
}
if(type==4){
x=read();
ptf("%d\n",qt_son(x));
}
}
// cout<<Mod<<endl;
return 0;
}
```
by swiftc @ 2019-07-10 20:26:38
@[東方零闇](/space/show?uid=116460)
by swiftc @ 2019-07-10 20:29:15
@[UIKIt](/space/show?uid=183154) 哇哇哇!QAQ
万分感谢!
by 澪lane @ 2019-07-10 20:33:40
@[UIKIt](/space/show?uid=183154) 谢谢您呐!
by 澪lane @ 2019-07-10 20:34:25
哈哈QVQ,厉害
by 已注销&M73*K7U @ 2019-07-10 21:11:30