今天也是为了解LCA，然后学了树链剖分
这边写个讲解
树剖分为重链剖分和长链剖分
通常指的是重链剖分
重链剖分
对于任意一个位于树上的节点
重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。
轻子节点 表示剩余的所有子结点
重边 表示这个结点到重子节点的边
轻边 表示这个结点到其他轻子节点的边为
重链 表示若干条首尾衔接的重边
把落单的结点也当作重链，那么整棵树就被剖分成若干条重链
借用一下OI-wiki的图片
实现
首先，要先预处理几个变量
每个结点的父节点，子树大小，深度，重子节点，所在重链的链顶，重边优先遍历时的DFS序，DFS序对应的结点编号
struct node{
int fa/*父节点*/,dep/*深度*/,siz/*子树大小*/,son/*重子节点*/,top/*所在链的链顶*/;
int dfn/*DFS序*/,rnk/*对应编号*/;
}T[MAXM];
预处理的方法就是两个DFS
- 第一遍：记录父节点，深度，子树大小，重子节点
inline void Dfs1(int q){
T[q].son=-1;
T[q].siz=1;
for(int j=head[q];j;j=NEXT[j]){
if(j=T[q].fa) continue;
T[j].dep=T[q].dep+1;
T[j].fa=q;
Dfs1(j);
T[q].siz+=T[j].siz;
if((T[q].son==-1)||(T[j].siz>T[T[q].son].siz)) T[q].son=j;
}
}
- 第二遍：记录所在链的链顶，DFS序，对应的rank
inline void Dfs2(int q,int v){
T[q].top=v;
T[q].dfn=++cnt;
T[cnt].rnk=q;
if(T[q].son==-1)
return;
Dfs2(T[q].son,v);
for(int j=head[q];j;j=NEXT[j]){
if((j!=T[q].fa)&&(j!=T[q].son))
Dfs2(j,j);
}
}
有啥用
首先，要用线段树维护
然后就可以
-
求树上两点路径权值和
-
维护子树上的信息(譬如将以\(x\)为根的子树的所有结点的权值增加\(v\))
-
求
LCA(\(O(\log n)\)甚至常数小)
根本思想：对于两个不在同一重链内的节点,让他们不断地跳,使得他们处于同一重链上
求树上两点路径权值和
这个比较抽象
首先，怎么跳？
根据一个显然的结论：x 到 T[x].top 中的节点在线段树上是连续的
结合深度dep
我们可以每次都让两个点的top中dep大的向上跳
每次跳直接让x跳到T[x].top即可，然后线段树上更新
在最后两个点处于同一重边时因为结论
x到T[x].top中的节点在线段树上是连续的
所以可以直接进行线段树的查询
子树操作
因为一棵树的子树在线段树上是连续的
所以直接线段树修改即可
LCA
这个和求树上两点路径权值和差不多一样(
就是更简单一些
只要知道树上倍增求LCA的应该也都懂
甚至不用线段树
代码实现
int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM];
namespace Grape{
inline void add(int u,int v){
NEXT[++tot]=head[u];
TO[tot]=v;
head[u]=tot;
}
}
namespace ST{
#define mid (l+r)/2
#define lC q<<1
#define rC q<<1|1
struct St{
long long l,r,siz;
long long lazy,dat;
}t[0x66ccff];
void build(int q,int l,int r){
t[q].l=l;
t[q].r=r;
t[q].siz=r-l+1;
if(l==r){
t[q].dat=a[l];
return;
}
build(lC,l,mid);
build(rC,mid+1,r);
t[q].dat=t[lC].dat+t[rC].dat;
}
void lazy(int q){
t[lC].lazy+=t[q].lazy;
t[lC].dat+=(t[lC].r-t[lC].l+1)*t[q].lazy;
t[rC].lazy+=t[q].lazy;
t[rC].dat+=(t[rC].r-t[rC].l+1)*t[q].lazy;
t[q].lazy=0;
}
void change(int q,int l,int r,int v){
if(t[q].l>r||t[q].r<l) return;
if(t[q].l>=l && t[q].r<=r){
t[q].lazy+=v;
t[q].dat+=(t[q].r-t[q].l+1)*v;
return;
}
if(t[q].lazy>0)
lazy(q);
change(lC,l,r,v);
change(rC,l,r,v);
t[q].dat=t[lC].dat+t[rC].dat;
}
long long asksum(int q,int l,int r){
if(t[q].l>r || t[q].r<l)
return 0;
if(t[q].l>=l && t[q].r<=r)
return t[q].dat;
if(t[q].lazy>0)
lazy(q);
return asksum(lC,l,r)+asksum(rC,l,r);
}
}
namespace killTree{
struct node{
int fa,dep,siz,son,top;
int dfn,rnk;
}T[MAXM];
inline void Dfs1(int q){
T[q].son=-1;
T[q].siz=1;
for(int j=head[q];j;j=NEXT[j]){
if(j=T[q].fa) continue;
T[j].dep=T[q].dep+1;
T[j].fa=q;
Dfs1(j);
T[q].siz+=T[j].siz;
if((T[q].son==-1)||(T[j].siz>T[T[q].son].siz)) T[q].son=j;
}
}
inline void Dfs2(int q,int v){
T[q].top=v;
T[q].dfn=++cnt;
T[cnt].rnk=q;
if(T[q].son==-1)
return;
Dfs2(T[q].son,v);
for(int j=head[q];j;j=NEXT[j]){
if((j!=T[q].fa)&&(j!=T[q].son))
Dfs2(j,j);
}
}
inline void TreeAdd(int x,int y,int val){
while(T[x].top!=T[y].top){
if(T[T[x].top].dep<T[T[y].top].dep)
std::swap(x,y);
ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
x=T[T[x].top].fa;
}
if(T[x].dep>T[y].dep)
std::swap(x,y);
ST::change(1,T[x].dfn,T[y].dfn,val);
}
inline int TreeSum(int x,int y){
int ans=0;
while(T[x].top!=T[y].top){
if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
ans=ans+ST::asksum(1,T[T[x].top].dfn,T[x].dfn);
x=T[T[x].top].fa;
}
if(T[x].dep>T[y].dep) std::swap(x,y);
return ans+ST::asksum(1,T[x].dfn,T[y].dfn);
}
inline void AddTree(int x,int y,int z){
ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,z);
}
inline int AskTree(){
ST::asksum(1,T[x].dfn,T[x].dfn+T[x].siz-1);
}
}