@[ChenZQ](/user/745358)
模板题——[This.](https://www.luogu.com.cn/problem/P3384)
by yjz468 @ 2024-04-27 09:47:21
示例代码：
```cpp
/*轻重链剖分/树链剖分*/
#include<bits/stdc++.h>
#define ls dep<<1
#define rs dep<<1|1
using namespace std;
const int Maxn = 1e5+10;
int N,M,R,P;
struct Edge{
int v;//节点编号
int next;
}edge[Maxn*2];
int head[Maxn];
int fa[Maxn];//记录父节点
int dep[Maxn];//记录节点深度
int son[Maxn];//记录重儿子
int siz[Maxn];//记录以该节点为根节点的树的大小（节点个数包括根节点）
int top[Maxn];//每一个节点所属重链的根节点
int dfn[Maxn];//每一个节点的时间戳
int w[Maxn];//dfs序后节点的权值,用线段树维护
int sum[Maxn*4];//线段树区间数组维护w[]区间和
int lazy[Maxn*4];//维护区间加的延迟数据,以便于延迟下方
int lpos[Maxn*4],rpos[Maxn*4];//线段树区间的左右端点
int tim = 0;//时间戳计数器
int cnt = 0;
int v[Maxn];//存放所有节点的权值
/*链式前向星建图,双向边*/
void build(int u,int v){
edge[++cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt;
edge[++cnt].v = u;
edge[cnt].next = head[v];
head[v] = cnt;
}
/*报一遍dfs记录重儿子，深度，以及子树大小*/
void dfs1(int u,int f){
fa[u] = f;
dep[u] = dep[f]+1;
siz[u] = 1;
int maxsonsize = -1;//记录重儿子的大小
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;//与u有边的节点
if(v==f) continue;//如果v时u的父亲，直接跳过
/*否则就是u的儿子,dfs下去*/
dfs1(v,u);
siz[u]+=siz[v];
/*更新u的重儿子*/
if(siz[v]>maxsonsize){
maxsonsize = siz[v];
son[u] = v;
}
}
}
/*再跑一边dfs，完成树链剖分*/
void dfs2(int u,int t){
dfn[u] = ++tim;//dfs序
top[u] = t;//u所属重链的祖先节点
w[tim] = v[u];//dfs序后的节点权值
/*没有重儿子，代表时根节点,直接return*/
if(!son[u]) return ;
dfs2(son[u],t);
for(int i=head[u];i!=-1;i=edge[i].next){
int v = edge[i].v;
//如果v时u的父节点，或者v时u的重儿子(已经遍历过了)
if(v==fa[u]||v==son[u]) continue;
/*否则以该节点为新的重链的祖先,继续dfs序*/
else dfs2(v,v);
}
return ;
}
/*更新区间和*/
void pushup(int dep){
sum[dep] = sum[ls]%P+sum[rs]%P;
sum[dep]%=P;
return ;
}
/*延迟更新,标记下放操作*/
void pushdown(int dep){
if(lazy[dep]){
lazy[rs]+=lazy[dep];
lazy[ls]+=lazy[dep];
lazy[rs]%=P;
lazy[ls]%=P;
sum[ls]+=lazy[dep]%P*(rpos[ls]-lpos[ls]+1)%P;
sum[rs]+=lazy[dep]%P*(rpos[rs]-lpos[rs]+1)%P;
sum[ls]%=P;
sum[rs]%=P;
lazy[dep] = 0;
}
return ;
}
/*建立线段树*/
void build_tree(int l,int r,int dep){
if(l==r){
sum[dep] = w[l]%P;
sum[dep]%=P;
lpos[dep]=rpos[dep]=l;
return ;
}
int mid = l+r>>1;
build_tree(l,mid,ls);
build_tree(mid+1,r,rs);
lpos[dep] = l;
rpos[dep] = r;
pushup(dep);//更新区间和
}
void modify(int l,int r,int ql,int qr,int dep,int val){
if(ql<=l&&r<=qr){
sum[dep]+=(r-l+1)%P*val%P;
sum[dep]%=P;
lazy[dep]+=val%P;
lazy[dep]%=P;
return ;
}
pushdown(dep);
int mid = l+r>>1;
if(ql<=mid) modify(l,mid,ql,qr,ls,val);
if(qr>mid) modify(mid+1,r,ql,qr,rs,val);
pushup(dep);
return ;
}
/*区间查询*/
int query(int l,int r,int ql,int qr,int dep){
if(ql<=l&&r<=qr){
return sum[dep]%P;
}
pushdown(dep);
int mid = l+r>>1;
int ans = 0;
if(ql<=mid) ans+=query(l,mid,ql,qr,ls);
if(qr>mid) ans+=query(mid+1,r,ql,qr,rs);
ans%=P;
return ans;
}
/*初始化函数*/
void init(){
memset(head,-1,sizeof(head));
return ;
}
/*操作1:x-y链上的所有节点加上z*/
void modifychain(int x,int y,int z){
z%=P;//因为答案要模P，所以先对z取模
/*节点x和y不在同一条重链上*/
while(top[x]!=top[y]){
/*先修改重链祖先更深的点，这样才能不断向上走合并为，
转移到一条重链上最后(有点抽象,画个图)*/
if(dep[top[x]]<dep[top[y]]) swap(x,y);
modify(1,N,dfn[top[x]],dfn[x],1,z);//区间修改
x = fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
modify(1,N,dfn[x],dfn[y],1,z);
return ;
}
/*操作2:树从 x 到 y 结点最短路径上所有节点的值之和*/
int querychain(int x,int y){
int ans = 0;
/*节点x和y不在同一条重链上*/
while(top[x]!=top[y]){
/*先修改重链祖先更深的点，这样才能不断向上走合并为，
转移到一条重链上最后(有点抽象,画个图)*/
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=query(1,N,dfn[top[x]],dfn[x],1);//区间修改
ans%=P;
x = fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query(1,N,dfn[x],dfn[y],1);
ans%=P;
return ans;
}
/*操作3:以x为根节点的子数内所有节点值都加上z*/
void modifyson(int x,int z){
/*因为一个节点的子树上的时间戳一定大于该节点，并且连续*/
modify(1,N,dfn[x],dfn[x]+siz[x]-1,1,z);//线段树维护的w[]数组的区间修改
}
/*操作4:求以x为根节点的子数内所有节点值之和*/
int queryson(int x){
return query(1,N,dfn[x],dfn[x]+siz[x]-1,1)%P;
}
/*
void t_sum(int l,int r,int dep){
if(l==r){
cout<<sum[dep]<<' '<<dep<<'\n';
return ;
}
int mid = l+r>>1;
t_sum(l,mid,ls);
t_sum(mid+1,r,rs);
return ;
}*/
int main()
{
init();
cin>>N>>M>>R>>P;//表示树的结点个数、操作个数、根节点序号和取模数
for(int i=1;i<=N;i++) cin>>v[i];
for(int i=1;i<N;i++){
int u,v;
cin>>u>>v;
build(u,v);
}
dfs1(R,R);
dfs2(R,R);
build_tree(1,N,1);
for(int i=1;i<=M;i++){
int op;
cin>>op;
if(op==1){
int x,y,z;
cin>>x>>y>>z;
modifychain(x,y,z);
}
else if(op==2){
int x,y;
cin>>x>>y;
cout<<querychain(x,y)%P<<'\n';
}
else if(op==3){
int x,z;
cin>>x>>z;
modifyson(x,z);
}
else if(op==4){
int x;
cin>>x;
cout<<queryson(x)%P<<'\n';
}
}
return 0;
}
```
by yjz468 @ 2024-04-27 09:48:00
@[yjz468](/user/937773) thx
by ChenZQ @ 2024-04-27 09:48:42
还有这个：[here](https://www.luogu.com.cn/problem/P3379)
by yjz468 @ 2024-04-27 09:48:47
@[ChenZQ](/user/745358) P4513 算不算模板 $KTT$ 简化版线段树
by kevinZ99 @ 2024-04-27 10:08:38
@[kevinZ99](/user/1117080) ？
by vflower @ 2024-04-27 12:01:54