https://www.luogu.org/problemnew/show/P3384
树链剖分模板，需要的自取
1 #define IO std::ios::sync_with_stdio(0); 2 #include <bits/stdc++.h> 3 #define iter ::iterator 4 using namespace std; 5 typedef long long ll; 6 typedef pair<ll,ll>P; 7 #define pb push_back 8 #define se second 9 #define fi first 10 #define rs o<<1|1 11 #define ls o<<1 12 #define inf 0x3f3f3f3f 13 const int N=1e5+5; 14 int n,q,rt,mod; 15 int a[N],b[N]; 16 vector<int>g[N]; 17 int deep[N],fa[N],id[N],son[N],siz[N],top[N]; 18 int sumv[N*4],add[N*4]; 19 int L[N*4],R[N*4]; 20 void dfs1(int u,int f){ 21 deep[u]=deep[f]+1; 22 fa[u]=f; 23 siz[u]=1; 24 int mx=-1; 25 for(int i=0;i<g[u].size();i++){ 26 int v=g[u][i]; 27 if(v==f)continue; 28 dfs1(v,u); 29 siz[u]+=siz[v]; 30 if(siz[v]>mx){ 31 mx=siz[v]; 32 son[u]=v; 33 } 34 } 35 } 36 int tim; 37 void dfs2(int u,int topf){ 38 id[u]=++tim; 39 a[tim]=b[u]; 40 top[u]=topf; 41 if(!son[u])return; 42 dfs2(son[u],topf); 43 for(int i=0;i<g[u].size();i++){ 44 int v=g[u][i]; 45 if(v==fa[u]||v==son[u])continue; 46 dfs2(v,v); 47 } 48 } 49 void push(int o){ 50 sumv[o]=(sumv[ls]+sumv[rs])%mod; 51 } 52 void down(int o){ 53 if(add[o]){ 54 add[o]%=mod; 55 sumv[ls]+=add[o]*(R[ls]-L[ls]+1); 56 sumv[ls]%=mod; 57 sumv[rs]+=add[o]*(R[rs]-L[rs]+1); 58 sumv[rs]%=mod; 59 add[ls]+=add[o]; 60 add[ls]%=mod; 61 add[rs]+=add[o]; 62 add[rs]%=mod; 63 add[o]=0; 64 } 65 } 66 void build(int o,int l,int r){ 67 if(l==r){ 68 sumv[o]=a[l]%mod; 69 L[o]=R[o]=l; 70 return; 71 } 72 int m=(l+r)/2; 73 build(ls,l,m); 74 build(rs,m+1,r); 75 L[o]=L[ls]; 76 R[o]=R[rs]; 77 push(o); 78 } 79 int qu(int o,int l,int r,int ql,int qr){ 80 if(l>=ql&&r<=qr){ 81 return sumv[o]%mod; 82 } 83 down(o); 84 int m=(l+r)/2; 85 int res=0; 86 if(ql<=m)res+=qu(ls,l,m,ql,qr)%mod; 87 res%=mod; 88 if(qr>m)res+=qu(rs,m+1,r,ql,qr)%mod; 89 res%=mod; 90 return res; 91 } 92 void up(int o,int l,int r,int ql,int qr,int v){ 93 if(l>=ql&&r<=qr){ 94 v%=mod; 95 add[o]+=v; 96 add[o]%=mod; 97 sumv[o]+=v*(r-l+1); 98 sumv[o]%=mod; 99 return; 100 } 101 down(o); 102 int m=(l+r)/2; 103 if(ql<=m)up(ls,l,m,ql,qr,v); 104 if(qr>m)up(rs,m+1,r,ql,qr,v); 105 push(o); 106 } 107 void qu1(int x,int y){//x节点到y节点的路径和 108 int res=0; 109 while(top[x]!=top[y]){ 110 if(deep[top[x]]<deep[top[y]])swap(x,y); 111 res+=qu(1,1,n,id[top[x]],id[x]); 112 res%=mod; 113 x=fa[top[x]]; 114 } 115 if(deep[x]>deep[y])swap(x,y); 116 res+=qu(1,1,n,id[x],id[y])%mod; 117 res%=mod; 118 printf("%d ",res); 119 } 120 void up1(int x,int y,int z){//把x节点到y节点的路径所有点加z 121 while(top[x]!=top[y]){ 122 if(deep[top[x]]<deep[top[y]])swap(x,y); 123 up(1,1,n,id[top[x]],id[x],z); 124 x=fa[top[x]]; 125 } 126 if(deep[x]>deep[y])swap(x,y); 127 up(1,1,n,id[x],id[y],z); 128 } 129 int main(){ 130 scanf("%d%d%d%d",&n,&q,&rt,&mod); 131 for(int i=1;i<=n;i++){ 132 scanf("%d",&b[i]); 133 b[i]%=mod; 134 } 135 for(int i=1;i<n;i++){ 136 int x,y; 137 scanf("%d%d",&x,&y); 138 g[x].pb(y); 139 g[y].pb(x); 140 } 141 dfs1(rt,0); 142 dfs2(rt,rt); 143 build(1,1,n); 144 while(q--){ 145 int op,x,y,z; 146 scanf("%d",&op); 147 if(op==1){//把x节点到y节点的路径所有点加z 148 scanf("%d%d%d",&x,&y,&z); 149 up1(x,y,z); 150 } 151 else if(op==2){//查询x节点到y节点的路径和 152 scanf("%d%d",&x,&y); 153 qu1(x,y); 154 } 155 else if(op==3){////把x节点的所有子孙加y 156 scanf("%d%d",&x,&y); 157 up(1,1,n,id[x],id[x]+siz[x]-1,y); 158 } 159 else{//查询x节点的子孙和 160 scanf("%d",&x); 161 printf("%d ",qu(1,1,n,id[x],id[x]+siz[x]-1)%mod); 162 } 163 } 164 }