题解 P3384 【【模板】树链剖分】
Dvelpro
2018-08-11 02:45:05
解释全部在代码之中 卿学姐的视频很不错
[一点就懂的 树剖](https://www.bilibili.com/video/av4482146?from=search&seid=16528902309319633365)
以下代码部分
```c
#include<bits/stdc++.h>
using namespace std;
#define maxn 500000+10
#define LL long long
LL no[maxn]; /// 所属链的编号
LL top[maxn]; /// top节点
LL dee[maxn]; /// 深度（然而我并没有用到）
LL fa[maxn]; /// 父亲节点
LL zs[maxn]; /// 重儿子
LL sz[maxn]; /// 子节点个数
LL dfn[maxn]; /// dfs的编号
LL tre[maxn]; /// 建树
LL a[maxn],b[maxn]; /// 储存节点的value
bool vis[maxn]; /// 第一遍 dfs 的标记数组
long long lz[maxn];/// 懒惰数组
vector<long long>q[maxn]; /// 记录节点信息
long long n,m,r,P;
long long tot=0,z=1; /// dfs的编号 和链的编号
void dfs(long long u,long long y){ ///第一遍dfs记录 节点的深度，重儿子，节点个数
sz[u]=1;
dee[u]=y;
long long mx=-1;
for(long long j=0;j<q[u].size();j++){
long long v=q[u][j];
if(!vis[v]){
vis[v]=1;
fa[v]=u;
dfs(v,y+1);
sz[u]+=sz[v];
if(sz[v]>mx){
mx=sz[v];
zs[u]=v;
}
}
}
}
void dfs2(long long u,long long y){ ///第二遍dfs 记录 每条链的编号以及每个节点的编号
dfn[u]=++tot;
b[tot]=a[u];
top[u]=y;
no[u]=z;
if(zs[u]==0) return ;
if(zs[u]){
dfs2(zs[u],y);
}
for(long long j=0;j<q[u].size();j++){
long long v=q[u][j];
if(v!=zs[u]&&v!=fa[u]){
z++;
dfs2(v,v);
}
}
}
void lazy(long long in,long long rt){
if(lz[in]){
lz[in*2]+=lz[in];
lz[in*2+1]+=lz[in];
tre[in*2]+=lz[in]*(rt-rt/2);
tre[in*2+1]+=lz[in]*(rt/2);
lz[in]=0;
}
}
void build(long long l,long long r,long long in){
if(l==r){
tre[in]=b[l];
return ;
}
long long mid=(l+r)/2;
build(l,mid,in*2);
build(mid+1,r,in*2+1);
tre[in]=tre[in*2]+tre[in*2+1];
}
long long query(long long l,long long r,long long x,long long y,long long in){
if(l==x&&r==y){
return tre[in]%P;
}
lazy(in,y-x+1);
long long mid=(x+y)/2;
if(r<=mid){
return query(l,r,x,mid,in*2)%P;
}else if(l>mid){
return query(l,r,mid+1,y,in*2+1)%P;
}
return (query(l,mid,x,mid,in*2)%P+query(mid+1,r,mid+1,y,in*2+1)%P)%P;
}
void updata(long long l,long long r,long long x,long long y,long long in,long long c){
if(l==x&&r==y){
tre[in]+=c*(y-x+1);
lz[in]+=c;
return ;
}
lazy(in,y-x+1);
long long mid=(x+y)/2;
if(r<=mid){
updata(l,r,x,mid,in*2,c);
}else if(l>mid){
updata(l,r,mid+1,y,in*2+1,c);
}
else{
updata(l,mid,x,mid,in*2,c);
updata(mid+1,r,mid+1,y,in*2+1,c);
}
tre[in]=tre[in*2]+tre[in*2+1];
}
/// 以上正常的线段树操作
void xiugai1(long long x,long long y,long long z){
long long xx=no[x],yy=no[y]; /// 属于那条链
if(xx==yy){ /// 判断链的编号大小然后做出修改
long long xxx=dfn[x],yyy=dfn[y]; /// 相同 属于同一条链 同一条链的编号是连续的
if(xxx>yyy) swap(xxx,yyy);
updata(xxx,yyy,1,n,1,z);
return ;
}
if(xx>yy){ /// x>y 修改x所在链的区间
updata(dfn[top[x]],dfn[x],1,n,1,z);
xiugai1(fa[top[x]],y,z); /// 递归寻找其top节点的父亲节点的链和y比较
}
if(xx<yy){
updata(dfn[top[y]],dfn[y],1,n,1,z);
xiugai1(x,fa[top[y]],z);
}
}
long long chaxun1(long long x,long long y){ /// 和修改操作基本一致
long long xx=no[x],yy=no[y];
if(xx==yy){
long long xxx=dfn[x],yyy=dfn[y];
if(xxx>yyy) swap(xxx,yyy);
return query(xxx,yyy,1,n,1)%P;
}
long long ans=0;
if(xx>yy){
ans+=query(dfn[top[x]],dfn[x],1,n,1)%P;
ans%=P;
ans+=chaxun1(fa[top[x]],y)%P;
ans%=P;
}
if(xx<yy){
ans+=query(dfn[top[y]],dfn[y],1,n,1)%P;
ans%=P;
ans+=chaxun1(x,fa[top[y]])%P;
ans%=P;
}
return ans%P;
}
long long chaxun(long long x){ /// 某一节点的子树的编号一定连续 只要找到 这个节点的sz个数和 dfn 编号即可
return query(dfn[x],dfn[x]+sz[x]-1,1,n,1)%P;
}
void xiugai(long long x,long long y){ /// 同上
updata(dfn[x],dfn[x]+sz[x]-1,1,n,1,y);
}
/// 以下就是常规的操作
int main(){
cin>>n>>m>>r>>P;
memset(lz,0,sizeof(lz));
for(long long j=1;j<=n;j++){
cin>>a[j];
}
memset(vis,0,sizeof(vis));
for(long long j=1;j<n;j++){
long long x,y;
cin>>x>>y;
q[x].push_back(y);
q[y].push_back(x);
}
vis[r]=1;
dfs(r,1LL*1);
memset(vis,0,sizeof(vis));
dfs2(r,r);
build(1,n,1);
for(long long j=0;j<m;j++){
long long nu,x,y,z;
cin>>nu;
if(nu==1){
cin>>x>>y>>z;
xiugai1(x,y,z);
}
if(nu==2){
cin>>x>>y;
cout<<chaxun1(x,y)%P<<endl;;
}
if(nu==3){
cin>>x>>y;
xiugai(x,y);
}
if(nu==4){
cin>>x;
cout<<chaxun(x)%P<<endl;
}
}
return 0；
}
```