厦门自助网站建设报价,广州安全教育平台视频,建设公司和建筑公司有什么区别,广州营销网站制作L C A LCA LCA#xff1a;树上两个点的最近公共祖先。#xff08;两个节点所有公共祖先中#xff0c;深度最大的公共祖先#xff09; L C A LCA LCA的性质#xff1a;
在所有公共祖先中#xff0c; L C A ( x , y ) LCA(x,y) LCA(x,y)到 x x x和 y y y的距离都最短。 x … L C A LCA LCA树上两个点的最近公共祖先。两个节点所有公共祖先中深度最大的公共祖先 L C A LCA LCA的性质
在所有公共祖先中 L C A ( x , y ) LCA(x,y) LCA(x,y)到 x x x和 y y y的距离都最短。 x x x y y y之间最短的路径经过 L C A ( x , y ) LCA(x,y) LCA(x,y)。 x x x y y y本身也可以是它们自己的公共祖先。若 y y y是 x x x的祖先则有 L C A ( x , y ) y LCA(x,y) y LCA(x,y)y。 L C A ( x , y , z ) L C A ( x , L C A ( y , z ) ) LCA(x,y,z) LCA(x, LCA(y,z)) LCA(x,y,z)LCA(x,LCA(y,z)) L C A ( x 1 , x 2 , . . . , x n ) L C A ( d f s 序最大点 d f s 序最小点 ) LCA(x_1, x_2,...,x_n) LCA(dfs序最大点dfs序最小点) LCA(x1,x2,...,xn)LCA(dfs序最大点dfs序最小点)
本文主要介绍求 L C A LCA LCA的两种方法倍增法和 T a r j a n Tarjan Tarjan。
先引入例题
【模板】LCA
题目描述
给定一个 n n n个点以结点 1 1 1为根的树有 q q q次询问每次询问给出两个点 u , v u,v u,v求 L C A ( u , v ) LCA(u,v) LCA(u,v)。 L C A ( u , v ) LCA(u,v) LCA(u,v)表示 u , v u,v u,v的最近公共祖先。
输入描述
第一行一个整数 n n n表示结点个数。 ( 1 ≤ n ≤ 2 × 1 0 5 ) (1 \leq n \leq 2 \times 10^5) (1≤n≤2×105)
第二行 n − 1 n−1 n−1个整数表示 2 ∼ n 2∼n 2∼n结点的父亲。
第三行一个整数 q q q表示询问次数。 ( 1 ≤ q ≤ 2 × 1 0 5 ) (1 \leq q \leq 2 \times 10^5) (1≤q≤2×105)
接下来 q q q行每行两个整数 u , v u,v u,v。 ( 1 ≤ u , v ≤ n ) (1≤u,v≤n) (1≤u,v≤n)
输出描述
对于每次询问一行一个整数表示结果。
输入样例1
5
1 1 2 3
3
1 2
2 4
1 5输出样例1
1
2
1倍增法
大体就是让两个点不断向上走直到走到最近的相同的点。如何快速地走这里就需要用倍增法来实现。倍增法的原理利用了二进制的性质任意一个数字都可以由一个或几个 2 2 2的幂相加得到所以可以以 1 , 2 , 4 , 8... 1,2,4,8... 1,2,4,8...这种 2 2 2的幂作为一步的长度向上走。
因为我们不知道应该走多大所以应该先尝试走大数能走即走再尝试走小步。
为了快速地进行跳跃我们需要预处理出一个帮助我们进行跳跃的数组 f a [ N ] [ 20 ] fa[N][20] fa[N][20] f a [ x ] [ i ] fa[x][i] fa[x][i]表示从 x x x出发向上走 2 i 2^{i} 2i步到达的位置。计算 f a fa fa数组时用到了 d p dp dp的思路这里有个递推公式 f a [ x ] [ i ] f a [ f a [ x ] [ i − 1 ] ] [ i − 1 ] fa[x][i] fa[fa[x][i - 1]][i - 1] fa[x][i]fa[fa[x][i−1]][i−1]意思是从点 x x x出发先跳 2 i − 1 2 ^ {i - 1} 2i−1步再跳 2 i − 1 2 ^ {i - 1} 2i−1步。由小推到大。
得到这个数组之后就可以快速地计算 L C A LCA LCA了。具体步骤如下
先将点 x x x和点 y y y处理至同一深度。让深度较大的数以祖先链上深度与深度较小的那个点相等的点为目标进行跳跃。特殊的如果该点就是深度较浅的那个点则使用上述 L C A LCA LCA的性质中的第三条。
之后点 x x x和点 y y y再同时向上跳跃。直至分别跳到 L C A ( x , y ) LCA(x,y) LCA(x,y)的两个儿子上。即 x ̸ y x \not y xy并且 f a [ x ] [ 0 ] f a [ y ] [ 0 ] fa[x][0] fa[y][0] fa[x][0]fa[y][0]。
最后得到的 f a [ x ] [ 0 ] fa[x][0] fa[x][0]就是 L C A ( x , y ) LCA(x,y) LCA(x,y)。
时间复杂度为 O ( n l o g 2 n q l o g 2 n ) O(nlog_2n qlog_2n) O(nlog2nqlog2n)
#includebits/stdc.h
using namespace std;
const int N 2e5 9, T 20;vectorint g[N];
int fa[N][30], dep[N];void dfs(int x)
{dep[x] dep[fa[x][0]] 1; //预处理各个节点深度//预处理fa数组for(int i 1; i T; i) fa[x][i] fa[fa[x][i - 1]][i - 1];for(const auto i : g[x]){dfs(i);}
}int lca(int u, int v)
{if(dep[u] dep[v]) swap(u, v); //不妨设点u深度大于等于点v//跳跃先走大步再走小步//将u点跳至于点v相同高度for(int i T; i 0; --i){if(dep[fa[u][i]] dep[v]) u fa[u][i];}if(u v) return u;//一起往上跳for(int i T; i 0; --i){if(fa[u][i] ! fa[v][i]) u fa[u][i], v fa[v][i];}return fa[u][0];
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n; cin n;for(int i 2; i n; i){cin fa[i][0];g[fa[i][0]].push_back(i);}dfs(1);int q; cin q;while(q--){int u, v; cin u v;cout lca(u, v) \n;}return 0;
}Tarjan
大概流程
还是采用 d f s dfs dfs访问到一个点的时候先标记被访问然后向下处理它的儿子节点看儿子节点是否为所求 L C A LCA LCA有关的点处理完儿子节点之后回溯上来时再处理自己看自己是否为所求 L C A LCA LCA有关的点。再向上合并合并采用并查集进行合并且使用路径压缩。
因为有多组询问所以需要将询问离线。
对于一对点中的一个点处理的时候若另一个点已经被访问过了那么那个点在的并查集中的根节点就是它们的 L C A LCA LCA这和 d f s dfs dfs的性质有关。都访问到的时候它们一定在同一棵子树上并且这颗子树的根显然就是它们的 L C A LCA LCA。
时间复杂度为 O ( n q ) O(n q) O(nq)
#includebits/stdc.h
using namespace std;
const int N 2e5 9;int pre[N], dep[N], ans[N], fa[N];
vectorint g[N];
vectorpairint, int Q[N];
bitsetN vis;//并查集基础操作
int find(int x)
{return pre[x] (pre[x] x ? x : find(pre[x]));
}void merge(int x, int y) //将深度大的向深度小的合并向上合并
{int fx find(x), fy find(y);if(dep[fx] dep[fy]) swap(fx, fy);pre[fx] fy;
}void dfs(int x)
{//顺手计算深度合并时使用dep[x] dep[fa[x]] 1;vis[x] true;for(const auto y : g[x]) dfs(y); //先处理所有儿子for(const auto [y, id] : Q[x]) //在处理自己{if(!vis[y]) continue; //如果对方未被访问就跳过ans[id] find(y);}merge(x, fa[x]);
}void solve()
{int n; cin n;for(int i 1; i n; i) pre[i] i;for(int i 2; i n; i){cin fa[i];g[fa[i]].push_back(i);}int q; cin q;//将询问离线for(int i 1; i q; i){int x, y; cin x y;Q[x].push_back({y, i});Q[y].push_back({x, i});}dfs(1);for(int i 1; i q; i) cout ans[i] \n;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ 1;while(_--) solve();return 0;
}L C A LCA LCA可以求树上两点之间的最短距离也可以做树上差分这里就不过多赘述。
