树链剖分
先讲解一下一些基础定义(都是在树上)
- 重儿子: 一个节点中所有儿子中子树大小最大的一个儿子(每个节点最多有一个重儿子)
- 轻儿子: 一个节点除重儿子外所有的节点
- 重链: 若干个重儿子组成的链
- 链顶: 一条链中深度最小的节点
以下图为例子 (红色连续线段为重链)
对于节点
1
1
1 来说, 子树大小最大的儿子是
2
2
2 ,
2
2
2 最大的是
5
5
5 ,
5
5
5的所有儿子子树大小一样大, 随机选一个即可
对于节点
3
3
3 来说, 虽然本身是一个轻儿子, 但是它有重儿子
4
4
4 , 所以也能构成一条重链
由此观之, 所有的点都在某条重链上(重链可能是一个点)
现在, 我们可以通过
d
f
s
dfs
dfs 求出以任意节点为根的子树大小, 并且通过全部比较找出每个节点的重儿子.
之后再次
d
f
s
dfs
dfs , 把重儿子连成一条又一条链, 记录每个节点所在链的链顶, 等会
L
C
A
LCA
LCA 要用
//知道原理就自己写吧, 我的码风一言难尽, 学长写了50行, 我写了270行, 删完之后还剩150行
void dfs(int now,int father){
for(int x=0;x<g[now].size();x++){
node to=g[now][x];
if(to.v==father){
continue;
}
fa[to.v]=now;
dfs(to.v,now);
siz[now]+=siz[to.v];
}
return;
}
void dfss(int now,int father){
int num=0,maxn=-1;
for(int x=0;x<g[now].size();x++){
node to=g[now][x];
if(to.v==father){
continue;
}
if(maxn<siz[to.v]){
maxn=siz[to.v];
num=to.v;
}
}
for(int x=0;x<g[now].size();x++){
node to=g[now][x];
if(to.v==father){
continue;
}
if(to.v==num){
chain_top[to.v]=chain_top[now];
}else{
chain_top[to.v]=to.v;
}
}
for(int x=0;x<g[now].size();x++){
if(g[now][x].v==father){
continue;
}
dfss(g[now][x].v,now);
}
return;
}
现在树剖完了, 就该 L C A LCA LCA 了
树链剖分LCA
有两个节点
A
,
B
A,B
A,B ,求它们最近公共祖先
L
C
A
LCA
LCA 的大致思想就是不断地往上跳, 直到两个节点到根的路径成包含关系时停止. 但是这个往上跳的过程很费时间, 于是我们可以通过某些判断, 让节点往上跳一条重链的长度(如图)
这棵树是挺大的
假设现在我要求
L
C
A
(
15
,
19
)
LCA(15,19)
LCA(15,19) 以下是具体操作步骤
- 判断当前两个节点的链顶是不是同一个点
- 若是, 则输出两个点中深度小的那个
- 若不是, 就让链顶深度最大的那个点往上跳, 跳到链顶的父亲节点
- 重复上述过程, 直到判断为是
要是没太明白的话就自己手动模拟以下:
int LCA(int a,int b){
while(ct[a]!=ct[b]){
if(dep[chain_top[a]]>=dep[chain_top[b]]){
a=fa[chain_top[a]];
}else{
b=fa[chain_top[b]];
}
}
if(dep[a]<dep[b]){
return a;
}else{
return b;
}
}
个人认为这个比倍增 L C A LCA LCA 好理解
例题
今天晚上更