解释一下代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>
inline T Min(T x,T y){
return x<y?x:y;
}
template<class T>
inline T Max(T x,T y){
return y<x?x:y;
}
template<class T>
inline void Swap(T &x,T &y){
T tmp=x;
x=y,y=tmp;
}
inline int read(){
int x=0,f=1;char ch=getchar();
while('0'>ch||'9'<ch){if(ch=='-') f=-f;ch=getchar();}
while('0'<=ch&&'9'>=ch){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}//自己写的一些函数
const int MAXN=100005;
struct LS{
int HEAD[MAXN],nxt[MAXN<<2],edge[MAXN<<2],tot;
inline void add(int u,int v){
edge[++tot]=v,nxt[tot]=HEAD[u],HEAD[u]=tot;
}
inline int head(int u){
return HEAD[u];
}
inline int nex(int i){
return nxt[i];
}
inline int operator[](int i){
return edge[i];
}
inline void clear(){
memset(HEAD,0,sizeof HEAD);
tot=0;
}
};
LS G;//链式前向星
int arr[MAXN];//原数组
int n=read(),m=read(),root=read(),M=read();//四个数
int siz[MAXN],son[MAXN],fa[MAXN],dep[MAXN];//树剖的东西
inline void dfs1(int u){
siz[u]=1,son[u]=-1;
for(int i=G.head(u);i;i=G.nex(i)){
int v=G[i];
if(v==fa[u]) continue;
fa[v]=u,dep[v]=dep[u]+1;
dfs1(v);
siz[u]+=siz[v];
if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
}
}
int top[MAXN],dfn[MAXN],rnk[MAXN],cnt;//同上
inline void dfs2(int u,int t){
top[u]=t;
dfn[u]=++cnt;
rnk[cnt]=u;
if(son[u]==-1) return;
dfs2(son[u],t);
for(int i=G.head(u);i;i=G.nex(i)) if(G[i]!=son[u]&&G[i]!=fa[u]) dfs2(G[i],G[i]);
}
struct ST{//结构体线段树
int sum[MAXN<<2],lazy[MAXN<<2];
inline void get(int rt){
sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%M;
}
inline void build(int rt,int l,int r){
if(l==r){
sum[rt]=arr[dfn[l]]%M;
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
get(rt);
}
inline void push_down(int rt,int l,int r,int mid){
lazy[rt<<1]=(lazy[rt<<1]+lazy[rt])%M,lazy[rt<<1|1]=(lazy[rt<<1|1]+lazy[rt])%M;
sum[rt<<1]=(sum[rt<<1]+lazy[rt]*(mid-l+1))%M,sum[rt<<1|1]=(sum[rt<<1|1]+lazy[rt]*(r-mid))%M;
lazy[rt]=0;
}
inline void updata(int rt,int l,int r,const int &L,const int &R,const int &val){
if(L<=l&&r<=R){
lazy[rt]=(lazy[rt]+val)%M;
sum[rt]=(sum[rt]+val*(r-l+1))%M;
return;
}
int mid=(l+r)>>1;
if(lazy[rt]) push_down(rt,l,r,mid);
if(L<=mid) updata(rt<<1,l,mid,L,R,val);
if(R>mid) updata(rt<<1|1,mid+1,r,L,R,val);
get(rt);
}
inline int query(int rt,int l,int r,const int &L,const int &R){
if(L<=l&&r<=R) return sum[rt];
int mid=(l+r)>>1;
if(lazy[rt]) push_down(rt,l,r,mid);
int ret=0;
if(L<=mid) ret=(ret+query(rt<<1,l,mid,L,R))%M;
if(R>mid) ret=(ret+query(rt<<1|1,mid+1,r,L,R))%M;
return ret;
}
};
ST t;
inline void change_road(int u,int v,int w){
w%=M;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) Swap(u,v);
t.updata(1,1,n,dfn[top[u]],dfn[u],w);
u=fa[top[u]];
}
if(dep[u]>dep[v]) Swap(u,v);
t.updata(1,1,n,dfn[u],dfn[v],w);
}
inline void change_tree(int u,int w){
t.updata(1,1,n,dfn[u],dfn[u]+siz[u]-1,w);
}
inline int query_road(int u,int v){
int ret=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) Swap(u,v);
ret=(ret+t.query(1,1,n,dfn[top[u]],dfn[u]))%M;
u=fa[top[u]];
}
if(dep[u]>dep[v]) Swap(u,v);
return (ret+t.query(1,1,n,dfn[u],dfn[v]))%M;
}
inline int query_tree(int u){
return t.query(1,1,n,dfn[u],dfn[u]+siz[u]-1)%M;
}//处理操作
int main(){
for(int i=1;i<=n;i++) arr[i]=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
G.add(u,v),G.add(v,u);
}
dfs1(root),dfs2(root,root);
t.build(1,1,n);
for(;m--;){
int op=read();
if(op==1){
int x=read(),y=read(),z=read();
change_road(x,y,z);
}
else if(op==2){
int x=read(),y=read();
printf("%d\n",query_road(x,y));
}
else if(op==3){
int x=read(),z=read();
change_tree(x,z);
}
else{
int x=read();
printf("%d\n",query_tree(x));
}
}
return 0;
}
```
by LQ2024 @ 2022-08-19 18:53:54
@[LQ2024](/user/673643) 线段树建树这一行
```cpp
sum[rt]=arr[dfn[l]]%M;
```
改成
```cpp
sum[rt]=arr[rnk[l]]%M;
```
by LoserKugua @ 2022-08-19 20:09:39
@[woshilaji_](/user/308796) 当时写着写着就混了,(我太蒻了。。),现在A了,谢谢
by LQ2024 @ 2022-08-19 21:02:04
@[LQ2024](/user/673643) 能不能顺便请您帮忙调一下蒟蒻写的树剖。。
```cpp
#include<cstdio>
#define maxn 200005
#define ll long long
using namespace std;
ll n,m,r,mod;
ll a[maxn],head[maxn],x1,y1,z1,op,tot;
ll father[maxn],depth[maxn],size[maxn],son[maxn],seg[maxn],rev[maxn],top[maxn];
struct edge{int to,next;}e[maxn<<1];
void swap(int &a,int &b){
int temp=a;
a=b;
b=temp;
}
inline void addedge(int u,int v){//邻接表存图
e[++tot].next=head[u];
e[tot].to=v;
head[u]=tot;
}
inline ll ffread(){//快读
ll ret=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){
ret=(ret<<1)+(ret<<3)+(c^48);
c=getchar();
}
return ret;
}
struct segtree{ll l,r,val,tag;}t[maxn<<2];
inline void spread(int p){
if(t[p].tag){
t[p<<1].val=(t[p<<1].val+t[p].tag*(t[p<<1].r-t[p<<1].l+1)%mod)%mod;
t[p<<1|1].val=(t[p<<1|1].val+t[p].tag*(t[p<<1|1].r-t[p<<1|1].l+1)%mod)%mod;
t[p<<1].tag=(t[p<<1].tag+t[p].tag)%mod;
t[p<<1|1].tag=(t[p<<1|1].tag+t[p].tag)%mod;
t[p].tag=0;
}
}
inline void build(int p,int l,int r){//建树
t[p].l=l;t[p].r=r;
if(l==r){
t[p].val=a[rev[l]];
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t[p].val=(t[p<<1].val+t[p<<1|1].val)%mod;
}
inline void change(int p,int l,int r,ll v){//区间修改
if(t[p].l>=l&&t[p].r<=r){
t[p].val=(t[p].val+v*(t[p].r-t[p].l+1)%mod)%mod;
t[p].tag=(t[p].tag+v)%mod;
return;
}
spread(p);
int mid=t[p].l+t[p].r>>1;
if(l<=mid)change(p<<1,l,r,v);
if(r>=mid+1)change(p<<1|1,l,r,v);
t[p].val=(t[p<<1].val+t[p<<1|1].val)%mod;
}
inline int ask(int p,int l,int r){//区间查询
if(t[p].l>=l&&t[p].r<=r)return t[p].val;
spread(p);
ll mid=t[p].l+t[p].r>>1,ret=0;
if(l<=mid)ret=(ret+ask(p<<1,l,r))%mod;
if(r>=mid+1)ret=(ret+ask(p<<1|1,l,r))%mod;
return ret;
}
void dfs1(int p,int fa){
size[p]=1;
father[p]=fa;
depth[p]=depth[fa]+1;
int v;
for(register int i=head[p];i;i=e[i].next){
v=e[i].to;
if(v==fa)continue;
dfs1(v,p);
size[p]+=size[v];
if(!son[p]||size[v]>size[son[p]])son[p]=v;
}
}
void dfs2(int p){
if(son[p]){//重链连续
seg[son[p]]=++seg[0];
top[son[p]]=top[p];
rev[seg[0]]=son[p];
dfs2(son[p]);
}
int v;
for(register int i=head[p];i;i=e[i].next){
v=e[i].to;
if(top[v])continue;//要么重儿子,要么父节点
seg[v]=++seg[0];
top[v]=v;//轻边<u,v>,则v为其所在链顶点
rev[seg[0]]=v;
dfs2(v);
}
}
void chunk_change(int x,int y,ll k){//两点间修改
k%=mod;
int fx=top[x],fy=top[y];
while(fx!=fy){
if(depth[fx]<depth[fy])swap(x,y),swap(fx,fy);//深度大的链顶向上修改
change(1,seg[fx],seg[x],k);
x=father[fx];
fx=top[x];
}
if(depth[x]>depth[y])swap(x,y);//还差丶
change(1,seg[x],seg[y],k);
}
int chunk_query(int x,int y){//两点间查询
int fx=top[x],fy=top[y],ret=0;
while(fx!=fy){
if(depth[fx]<depth[fy])swap(x,y),swap(fx,fy);
ret=(ret+ask(1,seg[fx],seg[x]))%mod;
x=father[fx];
fx=top[x];
}
if(depth[x]>depth[y])swap(x,y);
ret=(ret+ask(1,seg[x],seg[y]));
return ret;
}
void son_change(int x,int k){//子树修改
k%=mod;
change(1,seg[x],seg[x]+size[x]-1,k);
}
ll son_query(int x){//子树查询
return ask(1,seg[x],seg[x]+size[x]-1);
}
int main(){
n=ffread();m=ffread();r=ffread();mod=ffread();
for(register int i=1;i<=n;i++)a[i]=ffread();
for(register int i=1;i<=n-1;i++){
x1=ffread();
y1=ffread();
addedge(x1,y1);
addedge(y1,x1);
}
dfs1(r,0);
seg[r]=seg[0]=1;top[r]=rev[1]=r;//根节点链起始点
dfs2(r);
build(1,1,n);
while(m--){
op=ffread();
switch(op){
case 1:
x1=ffread(),y1=ffread(),z1=ffread();
chunk_change(x1,y1,z1);
break;
case 2:
x1=ffread(),y1=ffread();
printf("%d\n",chunk_query(x1,y1));
break;
case 3:
x1=ffread(),y1=ffread();
son_change(x1,y1);
break;
case 4:
x1=ffread();
printf("%d\n",son_query(x1));
break;
}
}
return 0;
}
```
by LoserKugua @ 2022-08-19 21:20:46
@[woshilaji_](/user/308796) 你线段树和查询函数最后结果没取模。。。
by LQ2024 @ 2022-08-20 13:16:59
@[woshilaji_](/user/308796) 我试了,取模之后就A了。。。
by LQ2024 @ 2022-08-20 13:17:43
@[LQ2024](/user/673643) 谢谢大佬
by LoserKugua @ 2022-08-20 15:10:40
@[LQ2024](/user/673643) 已经AC了谢谢
by LoserKugua @ 2022-08-20 15:13:37
@[woshilaji_](/user/308796) 不用谢
by LQ2024 @ 2022-08-20 15:36:52