树剖的一种应用 - 求 LCA

树剖也能搞 LCA 啦!

树剖的一种应用 - 求 LCA

LCA 有两种方法:

  • Tarjan 离线求 LCA
  • 倍增法求 LCA

今天我们来介绍另一种方法 —— 用树剖求 LCA

原理

树剖将一棵树剖成一条条的链,链的一头一定深度较浅,链的另一头一定深度较深。

通过这条链,我们可以 $O(1)$ 求出这条链的 LCA

如果两个点不在一条链怎么办?将这两个点跳到一条链上就行。

实现

树剖部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int n;
struct eddy
{
int to, next;
}edg_2[maxn];
int fir[maxm], eddy_tot;
int deep[maxm], ffather[maxm], son[maxm], size[maxm], head[maxm], out[maxm], ans[maxm];
void addedge(int f, int t)
{
edg_2[++ eddy_tot].to = t;
edg_2[eddy_tot].next = fir[f];
fir[f] = eddy_tot;
}
void dfs1(int u, int pre, int d)
{
deep[u] = d;
ffather[u] = pre;
son[u] = 0;
size[u] = 1;
for(int i = fir[u]; i; i = edg_2[i].next)
{
if(edg_2[i].to != pre)
{
dfs1(edg_2[i].to, u, d + 1);
size[u] += size[edg_2[i].to];
if(! son[u] || size[edg_2[i].to] > size[son[u]])
son[u] = edg_2[i].to;
}
}
}
void getpos(int u, int sp)
{
head[u] = sp;
if(son[u]) getpos(son[u], sp);
for(int i = fir[u]; i; i = edg_2[i].next)
{
if(edg_2[i].to != son[u] && edg_2[i].to != ffather[u])
getpos(edg_2[i].to, edg_2[i].to);
}
}

LCA 部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int LCA(int u, int v)
{
int f1 = head[u], f2 = head[v];
while(f1 != f2)
{
if(deep[f1] < deep[f2])
{
swap(f1, f2);
swap(u, v);
}
u = ffather[f1]; f1 = head[u];
}
if(u == v) return u;
if(deep[u] > deep[v]) swap(u, v);
return u;
}

未解决的问题

稍微再补充一些,并加入到板子里面。

找几道应用题。。

文章目录
  1. 1. 树剖的一种应用 - 求 LCA
    1. 1.1. 原理
    2. 1.2. 实现
      1. 1.2.1. 树剖部分
      2. 1.2.2. LCA 部分
  2. 2. 未解决的问题
{{ live2d() }}