树剖也能搞 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; }
|
未解决的问题
稍微再补充一些，并加入到板子里面。
找几道应用题。。
