清明在机房听学长讲树上差分时提到了 (LCA) 这个东西，就顺带着学习了一波。由于本人是个蒟蒻，为了避免出现看不懂自己写的 (Blog) 这种情况，文中涉及到的知识和概念都会 概括性地 讲一下。
先甩个定义
(LCA) ((Lowest) (Common) (Ancestors))
即最近公共祖先，是指在一个树或者有向无环图中同时拥有 (v) 和 (w) 作为后代的最深的节点，。在这里，我们定义一个节点也是其自己的后代，因此如果 (v) 是 (w) 的后代，那么 (w) 就是 (v) 和 (w) 的最近公共祖先。——参考自 (Wikipedia)
再贴个板子题链接：LuoguP3379 【模板】最近公共祖先（LCA）
题意：给定一颗有根多叉树的节点数、直连边、根节点，求节点 (a) 和节点 (b) 的 (LCA) 。
为方便，以下我们记节点 (a) 和节点 (b) 的 (LCA) 为 (lca(a,b)) 。
下面介绍四种求 (LCA) 的方法
- 倍增法
- (RMQ)
- (Tarjan)
- 树链剖分
倍增法
思路
先考虑最基本的想法，我们让它们中深度较大的节点往上“爬”，直至两节点深度相同，然后让它们同时往上“爬” ，相遇的节点既是 (lca(a,b)) 。这个想法的正确性显而易见，但如果我们是一个节点一个节点地“爬”的话，效率上行不通，所以我们考虑改进——让它们“爬”得快一点。倍增法，顾名思义，就是通过倍增“爬”的节点数来加快“爬”的速度。
实现
定义
- (dep[i]) ：节点 (i) 的深度。
- (far[i][j]) ：节点 (i) 往上“爬” (2^j) 个节点后到达的祖先节点。
这部分 (DFS) 一次预处理即可，比较简单，代码应该都看得懂，不讲。
不妨设 (dep[a] geq dep[b]) ，下面分两步走：
- 为了让节点 (a) 往上“爬”到与节点 (b) 同一深度的位置，我们不断令 (a=far[a][log_2(dep[a]-dep[b])]) ，直至 (dep[a]=dep[b])。 如果此时 (a=b) ，说明 (a) 即为所求 (LCA) ，否则继续下一步。
- 每次取最大的 (j) 使得 (far[a][j] eq far[b][j]) ，令 (a=far[a][j]) , (b=far[b][j]) ，直至 (far[a][0]=far[b][0]) 。此时，(far[a][0]) 即为所求 (LCA) 。
Code
#include <bits/stdc++.h>
using namespace std;
const int n_size=500005;
const int m_size=1e6+5;
const int bit_size=25;
int N,M,S,x,y,a,b;
int cnt,head[n_size],to[m_size],nxt[m_size];
int dep[n_size],far[n_size][bit_size],lg[n_size];
void add(int pre,int pos);
void dfs(int pre,int pos);
void prelg(void);
int lca(void);
int main(void){
scanf("%d%d%d",&N,&M,&S);
for(int i=1;i<N;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(0,S);
prelg();
for(int i=0;i<M;i++){
scanf("%d%d",&a,&b);
printf("%d
",lca());
}
return 0;
}
inline void add(int pre,int pos){
to[++cnt]=pos;
nxt[cnt]=head[pre];
head[pre]=cnt;
}
void dfs(int pre,int pos){
dep[pos]=dep[pre]+1;
far[pos][0]=pre;
for(int i=1;(1<<i)<=dep[pos];i++) far[pos][i]=far[far[pos][i-1]][i-1];
for(int i=head[pos];i>0;i=nxt[i])
if(to[i]!=pre) dfs(pos,to[i]);
}
void prelg(void){
for(int i=1;i<=N;i++) lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
}
int lca(void){
if(dep[a]<dep[b]) swap(a,b);
while(dep[a]>dep[b]) a=far[a][lg[dep[a]-dep[b]]];
if(a==b) return a;
for(int i=lg[dep[a]];i>=0;i--)
if(far[a][i]!=far[b][i]){
a=far[a][i];
b=far[b][i];
}
return far[a][0];
}
(RMQ)
甩个定义
(RMQ) ((Range) (Minimum) (Query))
即范围最值查询，是针对数据集的一种条件查询。若给定一个数组 (A[1,n]) ，范围最值查询指定一个范围条件 (i) 到 (j) ，要求取出 (A[i,j]) 中最大／小的元素。通常情况下，数组 (A) 是静态的，即元素不会变化，例如插入、删除和修改等，而所有的查询是以在线的方式给出的，即预先并不知道所有查询的参数。——参考自 (Wikipedia)
(RMQ) 算法主要借助于 (ST) 表
再甩一个定义
(ST) ((Sparse) (Table))
设要查询的静态数组为 (A[1,n]) ，创建一个二维数组 (ST[1,N][0,log_2N]) 。在这个数组中 (ST[i][j]) 表示 (A[i,i+2^j-1]) 中的最大／小值。——参考自 (Wikipedia)
看完定义是不是感觉 (ST) 表和倍增法中的数组 (far) 很像？实际上 (ST) 表在这里所起的作用确实和数组 (far) 是类似的。
前置知识
- 树的 (DFS) 序：遍历一棵树时节点的访问顺序。
- 树的欧拉序：遍历一棵树时途径节点所成的序列。
树的 (DFS) 序和欧拉序的联系：(DFS) 序就是去重的欧拉序（每个节点只保留首次出现的那个）。
思路
遍历树时，某个时刻会首次访问 (lca(a,b)) ，接着会遍历子树，不妨设先遍历的是节点 (a) 所在的子树，那么从首次访问节点 (a) 开始算起，接下来访问完节点 (a) 的子节点后会一路回溯到 (lca(a,b)) ，遍历完其他无关子树后接着再遍历节点 (b) 所在的子树，最后一路往下访问直到首次访问节点 (b) 为止。
记住这个过程：首次访问节点 (a) (
ightarrow) 回溯到 (lca(a,b)) (
ightarrow) 首次访问节点 (b)
这个过程对应的欧拉序涉及的所有节点中，(lca(a,b)) 是深度最小的节点。那么，求 (lca(a,b)) ，只需求欧拉序的这一段中深度最小的节点即可。
实现
定义
- (num[i]) ：欧拉序中第 (i) 个节点。
- (fap[i]) ：欧拉序中节点 (i) 首次出现的位置。
- (dep[i]) ：欧拉序中第 (i) 个节点的深度。
- (st[i][j]) ：(dep[i]) 最小值 (ST) 表，为了方便，我们存的是值的索引而不是值本身，即 (st[i][j]) 表示 (dep[i,i+2^j-1]) 中最小值的位置。
前面的三个数组 (DFS) 一次预处理，不讲。
(st[i][j]) 需要单独 (DP) 预处理，这里给出状态转移方程：
设 (x=st[i][j-1]) ，(y=st[i+2^{j-1}-1]][j-1]) ，则有
$$st[i][j]=egin{cases}
x & dep[x]<dep[y]
y & dep[x] geq dep[y]
end{cases}$$
边界条件是 (st[i][0]=i) ，比较好理解，不细讲。
最后是 (lca(a,b)) 的求法：
不妨设 (fap[a] leq fap[b]) ，我们只需找到 (ST) 表对 ([fap[a]),(fap[b]]) ，即我们所要的欧拉序段上的最小覆盖，即可利用 (ST) 表快速求出这一段中深度最小的节点。
设 (bit=log_2(fap[b]-fap[a]+1)) ，最小覆盖显然就是 ([fap[a],fap[a]+2^{bit}-1]) 和 ([fap[b]-2^{bit}+1,fap[b]]) ，即：
设 (x=st[fap[a]][bit]) ，(y=st[fap[b]-2^{bit}+1][bit]) ，则有
$$lca(a,b)=egin{cases}
x & dep[x]<dep[y]
y & dep[x] geq dep[y]
end{cases}$$
Code
#include <bits/stdc++.h>
using namespace std;
const int n_size=500005;
const int m_size=1e6+5;
const int bit_size=25;
int N,M,S,x,y,a,b;
int cnt,head[n_size],to[m_size],nxt[m_size];
int node,num[m_size],fap[n_size],dep[m_size];
int lg[m_size],st[m_size][bit_size];
void add(int pre,int pos);
void dfs_init(int pos,int predep);
void st_init(void);
int lca(void);
void prelg(void);
int main(void){
scanf("%d%d%d",&N,&M,&S);
for(int i=1;i<N;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs_init(S,0);
st_init();
for(int i=0;i<M;i++){
scanf("%d%d",&a,&b);
printf("%d
",lca());
}
return 0;
}
inline void add(int pre,int pos){
to[++cnt]=pos;
nxt[cnt]=head[pre];
head[pre]=cnt;
}
void dfs_init(int pos,int predep){
fap[pos]=++node;
num[node]=pos;
dep[node]=predep+1;
for(int i=head[pos];i>0;i=nxt[i])
if(fap[to[i]]==0){
dfs_init(to[i],dep[node]);
num[++node]=pos;
dep[node]=predep+1;
}
}
void st_init(void){
prelg();
for(int i=1;i<=node;i++) st[i][0]=i;
for(int i=1;i<=lg[node];i++){
int upp=node-(1<<i)+1;
for(int j=1;j<=upp;j++){
int x=st[j][i-1],y=st[j+(1<<(i-1))][i-1];
st[j][i]=dep[x]<dep[y]?x:y;
}
}
}
int lca(void){
if(fap[a]>fap[b]) swap(a,b);
int inc=fap[b]-fap[a]+1;
int sta=st[fap[a]][lg[inc]];
int stb=st[fap[b]-(1<<lg[inc])+1][lg[inc]];
if(dep[sta]<dep[stb]) return num[sta];
return num[stb];
}
void prelg(void){
for(int i=1;i<=node;i++) lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
}
(Tarjan)
前置知识
- 并查集 ((DSU))
应该都会吧
还是简单提一下吧~
甩定义
(DSU) ((Disjoint) (Sets) (Union))
即并查集，是一种树型的数据结构，用于处理一些不交集 ((Disjoint) (Sets)) 的合并及查询问题。
有一个联合-查找算法 ((Union) - (Find) (Algorithm)) 定义了两个用于此数据结构的操作：
(Find)：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
(Union)：将两个子集合并成同一个集合。——参考自 (Wikipedia)
先看定义，知道 (Find) 和 (Union) 操作是怎么回事再往下看，以下记 (find(x)) 为节点 (x) 所在集合的头，(far(x)) 为节点 (x) 在并查集中的父节点，(marge(a,b)) 为合并节点 (a) 和节点 (b) ，那么我们有
$$find(x)=egin{cases}
x & x=far(x)
far(x)=find(far(x)) & x
eq far(x)
end{cases}$$
这里实际上就是一个递归，画画图就懂了~
$$marge(a,b):far(find(a))=find(b)$$
这个也简单~
思路
先引用知乎上《如何理解 (Tarjan) 的 (LCA) 算法？》这一问题下高赞回答的一段话：
一个熊孩子 (Link) 从一棵有根树的最左边最底下的结点灌岩浆，(Link) 表示很讨厌这种倒着长的树。岩浆会不断的注入，直到注满整个树…如果岩浆灌满了一棵子树，(Link) 发现树的另一边有一棵更深的子树，(Link) 会先去将那棵子树灌满。岩浆只有在迫不得已的情况下才会向上升高，找到一个新的子树继续注入。机 ((yu)) 智 ((chun)) 的 (Link) 发现了找 (LCA) 的好方法，即如果两个结点都被岩浆烧掉时，他们的 (LCA) 即为那棵子树上岩浆最高的位置。
注意这段话中“如果两个结点都被岩浆烧掉时”这一句，实际上就是当节点 (a) ，(b) 都恰被访问过的时候。看完是不是想到了什么？是不是感觉和 (RMQ) 求 (LCA) 的思路差不多？没错，思路本质上是一样的，但实现则很不一样，(Tarjan) 找 (LCA) 的过程要更为巧妙。先明确一件事，当节点 (a) ，(b) 都恰被访问过时，我们还没有最终回溯到“岩浆最高的位置”，即 (lca(a,b)) ，记住这个这个性质。
遍历树时，某个时刻会首次访问 (lca(a,b)) ，接着会遍历子树，不妨设先遍历的是节点 (a) 所在的子树，我们每访问完一个节点及其子树并最终回溯到这个节点时，将这个节点标记为已访问，并把它和它的父节点用 (Union) 操作合并起来，令这个集合的祖先是它的父节点。当首次访问节点 (a) ( ightarrow) 回溯到 (lca(a,b)) 这个过程结束后，节点 (a) 所在子树上所有节点都已经和 (lca(a,b)) 合并成了一个集合，因为 (lca(a,b)) 还没有最终回溯，集合的祖先就一定是是 (lca(a,b)) ，接着一直到首次访问节点 (b) ，此时我们注意到节点 (a) 标记为已访问，亦即已与 (lca(a,b)) 合并，那么就可以判断 (a) 所在集合的祖先即 (lca(a,b)) 。注意，从这里可以看出，(Tarjan) 求 (lca(a,b)) 需要我们预先知道询问的节点 (a) 和节点 (b) ，也就是说这是一个离线算法，我们要预处理询问。
实现
定义
- (ans[i])：第 (i) 个询问的答案。
- (query[i]) ：与节点 (i) 有关的询问，除了存储另一个节点以外还要存储这是第几个询问，且与节点 (i) 有关的询问可能不止一个，故最好用 (pair) 类型的 (vector) 实现，这里令 (first) 为另一个节点，(second) 为询问的编号。
- (anc[i])：以节点 (i) 为头的集合的祖先。
- (vis[i])：节点 (i) 是否已访问。
(DFS) 遍历树，搜索到某一节点 (i) 时，先着搜索节点 (i) 的所有子节点，对于节点 (i) 的某一子节点 (j)，搜索节点 (j) 后 (marge(i,j)) ，并令 (anc[find(j)]=i)，搜索完所有子节点回溯到节点 (i) 时，令 (vis[i]=true) ，接着遍历 (query[i]) 看有无已访问的节点，若有已访问的节点，则 (ans[query[i][j].second]=anc[find(query[i][j].first)]) 。
实际上，我们每次令集合的头为当前节点的父节点就可以不使用数组 (anc) ，但有些优化过的并查集（比如我在这里用的按树高合并的并查集）不支持这样操作，所以这里还是选择使用这个数组，这样代码也更清晰。
Code
#include <bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define mp make_pair
typedef pair<int,int> pii;
const int n_size=500005;
const int m_size=1e6+5;
int N,M,S,x,y,a,b,ans[n_size];
vector<pii> query[n_size];
int cnt,head[n_size],to[m_size],nxt[m_size];
int far[n_size],rk[n_size],anc[n_size];
bool vis[n_size];
void add(int pre,int pos);
void lca(int pos,int pre);
void dsu_init(void);
void marge(int x,int y);
int find(int x);
int main(void){
scanf("%d%d%d",&N,&M,&S);
for(int i=1;i<N;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=1;i<=M;i++){
scanf("%d%d",&a,&b);
query[a].push_back(mp(b,i));
query[b].push_back(mp(a,i));
}
dsu_init();
lca(S,0);
for(int i=1;i<=M;i++) printf("%d
",ans[i]);
return 0;
}
inline void add(int pre,int pos){
to[++cnt]=pos;
nxt[cnt]=head[pre];
head[pre]=cnt;
}
void dsu_init(void){
for(int i=1;i<=N;i++) far[i]=i;
}
void lca(int pos,int pre){
for(int i=head[pos];i>0;i=nxt[i])
if(to[i]!=pre&&vis[to[i]]==false){
lca(to[i],pos);
marge(to[i],pos);
anc[find(to[i])]=pos;
}
vis[pos]=true;
int upp=query[pos].size();
for(int i=0;i<upp;i++){
int x=query[pos][i].fir,y=query[pos][i].sec;
if(ans[y]==0&&vis[x]==true) ans[y]=anc[find(x)];
}
}
void marge(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
if(rk[x]<rk[y]) far[x]=y;
else{
far[y]=x;
if(rk[x]==rk[y]) rk[x]++;
}
}
int find(int x){
if(x==far[x]) return x;
return far[x]=find(far[x]);
}
树链剖分
刚写完板子顺便温习一下！~
其实没有想象中的那么难~
这个人已经忘记了第一次写调了两三个小时还是写炸了的事实
之前不会树剖的可以借这个问题学习一下~
树链剖分
指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组 ((BIT))、二叉搜索树 ((BST))、伸展树 ((Splay))、线段树 ((Segment) (Tree)) 等）来维护每一条链。——参考自 (Baidupedia)
先引入几个概念
- 重儿子：父节点的节点数最多的子树的根节点。
- 轻儿子：不是重儿子的子节点。
- 重边：连接父节点和重儿子的边。
- 轻边：连接父节点和轻儿子的边。
- 重链：重边组成的链。
- 轻链：轻边组成的链。
思路
我们要做的就是把数分成重链和轻链。然后就好办了，分两种情况：
若节点 (a) 和节点 (b) 在同一条链上，那么深度较小的即是 (lca(a,b)) 。
否则，不断令链端深度较大的节点为它的链端的父节点，直至两节点在同一条链上，此时便转换为了第一种情况。
实现
定义
- (dep[i])：节点 (i) 的深度。
- (siz[i])：以节点 (i) 为根的树的节点数。
- (far[i]): 节点 (i) 的父节点。
- (son[i])：节点 (i) 的重儿子。
- (top[i])：节点 (i) 所在链的链端。
用两次 (DFS) 预处理这些东西，树剖就算做完了~第一次 (DFS) 除数组 (top) 外都预处理了，这部分正常 (DFS) 遍历树即可，不细讲。重点是 (top) 的预处理，我们搜索到一个节点时，如果该节点不为叶节点，那么重儿子要和轻儿子区分开来搜索！知道这一点后代码应该也能 很简单地 写出来叭qwq
接着求 (lca(a,b)) ，把思路翻译过来，很简单~
若 (top[a]=top[b]) ，设 (dep[a] leq dep[b]) ，则 (lca(a,b)=a) 。
否则，设每次操作后两节点中链端深度较大的节点为 (k) ，则不断令 (k=far[top[k]]) ，直至 (top[a]=top[b]) ，此时便转换为了第一种情况。
Code
#include <bits/stdc++.h>
using namespace std;
const int n_size=500005;
const int m_size=1e6+5;
int N,M,S,x,y,a,b;
int cnt,head[n_size],to[m_size],nxt[m_size];
int dep[n_size],siz[n_size],far[n_size],son[n_size],top[n_size];
void add(int pre,int pos);
void dfs_init_fir(int pos);
void dfs_init_sec(int pos,int tpos);
int lca(void);
int main(void){
scanf("%d%d%d",&N,&M,&S);
for(int i=1;i<N;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs_init_fir(S);
dfs_init_sec(S,S);
for(int i=0;i<M;i++){
scanf("%d%d",&a,&b);
printf("%d
",lca());
}
return 0;
}
inline void add(int pre,int pos){
to[++cnt]=pos;
nxt[cnt]=head[pre];
head[pre]=cnt;
}
void dfs_init_fir(int pos){
dep[pos]=dep[far[pos]]+1;
siz[pos]=1;
int son_siz=0;
for(int i=head[pos];i>0;i=nxt[i])
if(to[i]!=far[pos]){
far[to[i]]=pos;
dfs_init_fir(to[i]);
siz[pos]+=siz[to[i]];
if(siz[to[i]]<=son_siz) continue;
son[pos]=to[i];
son_siz=siz[to[i]];
}
}
void dfs_init_sec(int pos,int tpos){
top[pos]=tpos;
if(son[pos]>0) dfs_init_sec(son[pos],tpos);
for(int i=head[pos];i>0;i=nxt[i])
if(to[i]!=far[pos]&&to[i]!=son[pos]) dfs_init_sec(to[i],to[i]);
}
int lca(void){
while(top[a]!=top[b])
if(dep[top[a]]<dep[top[b]]) b=far[top[b]];
else a=far[top[a]];
return dep[a]<dep[b]?a:b;
}
(LCA) 的解法就这么 愉快地 讲完了呢~
我们小结一下四种解法的特点
- 倍增法：好理解，也好实现，较快~
- (RMQ) ：就你最慢了，哼唧~
可能是我写得菜 - (Tarjan) ：意外地挺好写，嘤~
- 树链剖分：虽然很多人说没必要用这个写，但评测姬显示这个是最快的呢~ 就求 (LCA) 这个问题来说，代码量也只比倍增法稍多一点而已嘤~
反正树剖天下第一！！！