关于树剖
wenge
2021-04-07 20:10:21
## 树剖是啥？
### 树剖就是分块——slh
广义的树剖指把一个树拆成若干条链。方法有多种，比如重链剖分，长链剖分等
狭义的树剖专指重链剖分。接下来只讨论最常用的重链剖分。
定义一个有根树上，一个结点子树大小最大的儿子为**重儿子**。其余的为轻儿子。如果多个儿子子树大小相同，则任选一个。如果没有儿子，就没有重儿子。
定义从一个点连向其重儿子的边叫**重边**，连向其余儿子的叫**轻边**。
定义由若干点和重边组成的一条链为**重链**。特别的，落单的一个节点也是重链。定义一条重链中深度最小的点为这条重链的**顶**。
## 树剖有啥性质？
重链剖分将树分割成不超过$O(\log n)$条重链。
每条重链、每个子树内dfs序连续。（对于每个点，优先dfs其重儿子的前提下）
## 树剖怎么做？
2次dfs维护7个数组。~~召唤神龙~~
dfs1()对于一个点维护其 父亲fa[],深度dep[],子树大小size[],重儿子hson[]
dfs2()对于一个点维护其 所在重链的顶top[],dfs序dfn[],满足rnk[dfn[x]]=x的值（有时用不到）rnk[]
细节参见代码。
std:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define $ 500005
ll n,r;//r为根
ll fa[$],dep[$],size[$],hson[$];
ll top[$],dfn[$],rnk[$];
ll tot=0;
void dfs1(ll x,ll z){//x是当前节点，z是父亲
fa[x]=z;//求出父亲
dep[x]=dep[z]+1;//求出深度
size[x]=1;//当前节点的大小为1
ll t=0;
for(int i=0;i<f[x].size();i++){
ll y=f[x][i];
if(y==z)continue;
dfs1(y,x);
size[x]+=size[y];//统计子树的大小
if(size[y]>t){
t=size[y];
hson[x]=y;//更新重儿子
}
}
}
void dfs2(ll x,ll t){//x是当前节点，z是x所在重链的顶
top[x]=t;//求出链顶
dfn[x]=++tot;//求出dfn
rnk[tot]=x;
if(hson[x]!=0){
dfs2(hson[x],t);//必须先dfs重儿子才能保证dfn的连续性质
for(int i=0;i<f[x].size();i++){//dfs轻儿子
ll y=f[x][i];
if(y==hson[x]||y==fa[x])continue;
dfs2(y,y);
}
}
}
```
```
int main(){//调用的方法
//......
dfs1(r,0);
dfs2(r,r);
//......
return 0;
}
```
## 树剖有啥用？
~~切题~~
### 1.求lca。
方法是：重复深度较深的点跳到他链顶的父亲（向上跳链），直到跳到同一链上。此时深度较小的点即为lca。
我之前打洛谷lca板子用倍增+vector被卡常了。树剖+vector屹立不倒。挺快。
实际应用还要考虑哪个维护题目中所使用的附加信息方便。
std:
```cpp
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define clr(a,b) memset(a,b,sizeof(a))
#define $ 500005
ll n,p,r;
ll a[$];
vector<ll> f[$];
ll fa[$],dep[$],size[$],hson[$];
ll top[$],dfn[$],rnk[$];
ll tot=0;
void dfs1(ll x,ll z){
fa[x]=z;
dep[x]=dep[z]+1;
size[x]=1;
ll t=0;
for(int i=0;i<f[x].size();i++){
ll y=f[x][i];
if(y==z)continue;
dfs1(y,x);
size[x]+=size[y];
if(size[y]>t){
t=size[y];
hson[x]=y;
}
}
}
void dfs2(ll x,ll t){
top[x]=t;
dfn[x]=++tot;
rnk[tot]=x;
if(hson[x]!=0){
dfs2(hson[x],t);
for(int i=0;i<f[x].size();i++){
ll y=f[x][i];
if(y==hson[x]||y==fa[x])continue;
dfs2(y,y);
}
}
}
ll lca(ll x,ll y){
while(top[x]!=top[y]){
if(dep[top[x]]>=dep[top[y]])x=fa[top[x]];
else y=fa[top[y]];
}
if(dep[x]<=dep[y])return x;
return y;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll q;
cin>>n>>q>>r;
//for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++){
ll u,v;
cin>>u>>v;
f[u].pb(v);f[v].pb(u);
}
dfs1(r,0);
dfs2(r,r);
for(int i=1;i<=q;i++){
ll u,v;
cin>>u>>v;
cout<<lca(u,v)<<"\n";
}
return 0;
}
```
### 2.维护树上信息
能够配合线段树、树状数组等数据结构维护树上信息。
例子：给你一棵树，点带权，4个操作：
1. 点x到点y的路径上点权增加a
1. 查询点x到点y的路径上点权之和
1. 以x为根的子树所有点权增加a
1. 询以x为根的子树所有点权之和
先看操作4。上面的性质告诉我们一个子树的dfs序连续。
对于点权建立线段树（或者树状数组），其中线段树第i个值是dfn为i的点的点权。
由于整个子树在线段树里都是一个连续的区间，并且维护了子树大小size[x]。所以直接对区间[dfn[x],dfn[x]+size[x]-1]进行区间求和即可。操作3同理，只需把区间求和改成区间加。复杂度$O(\log n)$。
再看操作2。操作2中的路径可以分成若干连续部分，每一部分在一条重链上。于是对这些部分分别区间求和即可。求和实现类似于上面lca的求法。具体见代码。操作1同理。由于整棵树不超过$O(\log n)$条重链，所以至多拆成$O(\log n)$部分，每次求和$O(\log n)$。所以复杂度$O(\log^2 n)$。于是就做完了。
同样可以解决路径赋值、子树赋值等问题。
```cpp
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define clr(a,b) memset(a,b,sizeof(a))
#define $ 100005
ll n,slh,r;
ll a[$],b[$];
vector<ll> f[$];
ll fa[$],dep[$],size[$],hson[$];
ll top[$],dfn[$],rnk[$];
ll tot=0;
void dfs1(ll x,ll z){
fa[x]=z;
dep[x]=dep[z]+1;
size[x]=1;
ll t=0;
for(int i=0;i<f[x].size();i++){
ll y=f[x][i];
if(y==z)continue;
dfs1(y,x);
size[x]+=size[y];
if(size[y]>t){
t=size[y];
hson[x]=y;
}
}
}
void dfs2(ll x,ll t){
top[x]=t;
dfn[x]=++tot;
a[tot]=b[x];//点权在此处整理，准备好建立线段树
rnk[tot]=x;
if(hson[x]!=0){
dfs2(hson[x],t);
for(int i=0;i<f[x].size();i++){
ll y=f[x][i];
if(y==hson[x]||y==fa[x])continue;
dfs2(y,y);
}
}
}
struct node{
ll x,add;
}sgt[4*$];
void pushup(ll i){
sgt[i].x=(sgt[i*2].x+sgt[i*2+1].x)%slh;
}
void pushdown(ll mid,ll l,ll r,ll i){
if(sgt[i].add){
sgt[i*2].x=(sgt[i*2].x+(mid-l+1)*sgt[i].add)%slh;
sgt[i*2+1].x=(sgt[i*2+1].x+(r-mid)*sgt[i].add)%slh;
sgt[i*2].add=(sgt[i*2].add+sgt[i].add)%slh;
sgt[i*2+1].add=(sgt[i*2+1].add+sgt[i].add)%slh;
sgt[i].add=0;
}
}
void build(ll l,ll r,ll i){
if(l==r){
sgt[i].x=a[l]%slh;
return;
}
ll mid=(l+r)>>1;
build(l,mid,i*2);
build(mid+1,r,i*2+1);
pushup(i);
}
ll query(ll s,ll t,ll l,ll r,ll i){
if(s<=l&&r<=t){
return sgt[i].x;
}
ll mid=(l+r)>>1;
pushdown(mid,l,r,i);
ll res=0;
if(s<=mid)res+=query(s,t,l,mid,i*2);
if(t>mid)res+=query(s,t,mid+1,r,i*2+1);
pushup(i);
return res%slh;
}
void modify(ll s,ll t,ll l,ll r,ll i,ll x){
if(s<=l&&r<=t){
sgt[i].x+=(r-l+1)*x;
sgt[i].add+=x;
return;
}
ll mid=(l+r)>>1;
pushdown(mid,l,r,i);
if(s<=mid)modify(s,t,l,mid,i*2,x);
if(t>mid)modify(s,t,mid+1,r,i*2+1,x);
pushup(i);
}
void op1(ll x,ll y,ll z){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
modify(dfn[top[x]],dfn[x],1,n,1,z);
x=fa[top[x]];
}
if(dfn[x]>dfn[y])swap(x,y);
modify(dfn[x],dfn[y],1,n,1,z);
}
ll op2(ll x,ll y){
ll res=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
res=(res+query(dfn[top[x]],dfn[x],1,n,1))%slh;
x=fa[top[x]];
}
if(dfn[x]>dfn[y])swap(x,y);
res=(res+query(dfn[x],dfn[y],1,n,1))%slh;
return res;
}
void op3(ll x,ll z){
modify(dfn[x],dfn[x]+size[x]-1,1,n,1,z);
}
ll op4(ll x){
return query(dfn[x],dfn[x]+size[x]-1,1,n,1);
}
int main(){
//freopen("P1429_6.in","r",stdin);
//freopen("match.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
ll q;
cin>>n>>q>>r>>slh;
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<n;i++){
ll u,v;
cin>>u>>v;
f[u].pb(v);f[v].pb(u);
}
dfs1(r,0);
dfs2(r,r);
build(1,n,1);
while(q--){
ll op;
cin>>op;
if(op==1){
ll x,y,z;
cin>>x>>y>>z;
op1(x,y,z);
}
if(op==2){
ll x,y;
cin>>x>>y;
cout<<op2(x,y)<<"\n";
}
if(op==3){
ll x,z;
cin>>x>>z;
op3(x,z);
}
if(op==4){
ll x;
cin>>x;
cout<<op4(x)<<"\n";
}
}
return 0;
}
```