当前位置:网站首页>Three methods of finding LCA of the nearest common ancestor
Three methods of finding LCA of the nearest common ancestor
2022-07-02 13:14:00 【litian355】
The definition of recent common ancestor : If the node c Satisfy :
Catalog
3. Use offline tarjan Algorithm for LCA Time complexity O(n+m)
1.c yes a and b The public ancestor node of .
2.c It's distance a,b The nearest public ancestor node .
Then call it c yes a and b The latest public ancestor of .
1. Upward marking method
Respectively from the a, Mark all a The ancestor node of , let b Jump up , The node that first encounters a tag is the nearest common ancestor .
n Node time complexity O(n*n)
2. Doubling Algorithm
step1: Preprocess all points from the top 2 Of k Who is the father of power ,fa[i][j] From i Start walking up 2 Of j The node to which the power can go
0<=j<=log2(n)
At the same time, preprocess the depth of each node depth[i].
step2: seek x,y The latest public ancestor of :
1. hypothesis x Depth ratio of y Big , That is to say x stay y Below , First, let x Multiply jump to and y At the same depth ( enumeration 2 Omega to an integer power )
2. Let the two points jump up at the same time , Jump to the next level of the nearest public ancestor , The answer is fa[a][0] perhaps fa[b][0];
Time complexity O(n*logn);
3. Use offline tarjan Algorithm for LCA Time complexity O(n+m)
1. The graph is divided into three categories by depth first traversal, and the representative elements of each traversed point are obtained by using the union search set :
0. No access points
1. The point being searched
2. Points that have been traversed
2. All the nearest common ancestors that have traversed the point associated with the point set being searched are the representative elements of this point .
Be careful : Because it is an offline algorithm, it needs to store each query and the answer of each query .
1172. Grandson asked
Given a tree containing n A rooted undirected tree of nodes , Node numbers are different from each other , But not necessarily 1∼n.
Yes m A asked , Each query gives a pair of node numbers x and y, inquiry x And y The relationship between our ancestors and grandchildren .
Input format
The first line of input includes an integer Represents the number of nodes ;
Next n One pair of integers per line a and b, Express a and b There is an undirected edge between them . If b yes −1, that a It's the root of the tree ;
The first n+2 The row is an integer m Number of questions ;
Next m That's ok , Two different positive integers per line x and y, It's a question .
Output format
For each inquiry , if x yes y Our ancestors output 1, if y yes x Our ancestors output 2, Otherwise output 0.
Data range
1≤n<=4e4,
1≤ The number of each node ≤4e4
sample input :
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19
sample output :
1
0
0
0
2
Naked LCA, Doubling Algorithm .
code:
// Use the multiplication algorithm to find the nearest common ancestor
//1. Let node a、b The same depth
//2. Let node a、b Jump to the LCA The next layer of .
#include<bits/stdc++.h>
using namespace std;
int n,m;
int root;
const int N=4e4+10,M=N*2;
int h[N],e[M],ne[M],idx;
int fa[N][16];
int depth[N];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int q[N];
void bfs(){
int hh=0,tt=0;
memset(depth,0x3f,sizeof depth);
q[0]=root;
depth[0]=0;
depth[root]=1;
while(hh<=tt){
int t=q[hh++];
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(depth[j]>depth[t]+1){
depth[j]=depth[t]+1;
q[++tt]=j;
fa[j][0]=t;
for(int k=1;k<=15;k++){
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
}
int lca(int a,int b){
if(depth[a]<depth[b]) swap(a,b);
for(int i=15;i>=0;i--){
if(depth[fa[a][i]]>=depth[b]){
a=fa[a][i];
}
}
if(a==b) return a;
for(int i=15;i>=0;i--){
if(depth[fa[a][i]]!=depth[fa[b][i]])
{
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
signed main(){
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
if(b==-1) root=a;
else add(a,b),add(b,a);
}
bfs();
cin>>m;
while(m--){
int a,b;
cin>>a>>b;
int p=lca(a,b);
if(p==a) cout<<1<<endl;
else if(p==b) cout<<2<<endl;
else cout<<0<<endl;
}
return 0;
}
1171. distance
give n A tree at a point , Ask for the shortest distance between two points many times .
Be careful :
- Side is Undirected Of .
- The number of all nodes is 1,2,…,n
Input format
The first line is two integers n and m.n Represents the number of points ,m It means the number of inquiries ;
Come down n−1 That's ok , Three integers per row x,y,k, Indication point x Sum point y There is an edge between which the length is k;
Next m That's ok , Two integers per line x,y, Indicates a query point x point-to-point y The shortest distance .
The node number in the tree is from 1 To n.
Output format
common m That's ok , For each inquiry , Output a line of query results .
Data range
2≤n≤1e4
1≤m≤2×1e4
0<k≤100
1≤x,y≤n
sample input 1:
2 2
1 2 100
1 2
2 1
sample output 1:
100
100
sample input 2:
3 2
1 2 10
3 1 15
1 2
3 2
sample output 2:
10
25
Ideas , For two nodes in the tree x,y We can use the formula for the distance between dist[x],dist[y] ,dist[lca(x,y)] , respectively x,y, as well as x and y The distance from the nearest common ancestor of to the root node .
that distance=dist[x]+dist[y]-2*dist[lca(x,y)];
code:
// Treelike tarjan Algorithm offline calculation LCA
//1. Find the distance from each point in the tree to the root node
//2. use tarjan The algorithm classifies the midpoint , Update and u About the node LCA to update dist
//
//
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 10010, M = N * 2;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int p[N];
int res[M];
int st[N];
vector<PII> query[N]; // first Another query save point ,second Save query number
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u, int fa)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
dist[j] = dist[u] + w[i];
dfs(j, u);
}
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void tarjan(int u)
{
st[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j])
{
tarjan(j);
p[j] = u;
}
}
for (auto item : query[u])
{
int y = item.first, id = item.second;
if (st[y] == 2)
{
int anc = find(y);
res[id] = dist[u] + dist[y] - dist[anc] * 2;
}
}
st[u] = 2;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
if (a != b)
{
query[a].push_back({b, i});
query[b].push_back({a, i});
}
}
for (int i = 1; i <= n; i ++ ) p[i] = i;
dfs(1, -1);
tarjan(1);
for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);
return 0;
}
边栏推荐
- Domestic free data warehouse ETL dispatching automation operation and maintenance expert taskctl
- Lucky numbers in the [leetcode daily question] matrix
- Package management tools
- Linear DP acwing 898 Number triangle
- js1day(輸入輸出語法,數據類型,數據類型轉換,var和let區別)
- Unity SKFramework框架(二十一)、Texture Filter 贴图资源筛选工具
- West digital decided to raise the price of flash memory products immediately after the factory was polluted by materials
- Jerry's watch reads the alarm clock [chapter]
- How to get the operating system running PHP- How to get the OS on which PHP is running?
- linux下清理系统缓存并释放内存
猜你喜欢
Linear DP acwing 902 Shortest editing distance
Tencent three sides: in the process of writing files, the process crashes, and will the file data be lost?
Js3day (array operation, JS bubble sort, function, debug window, scope and scope chain, anonymous function, object, Math object)
Unity skframework Framework (XVI), package manager Development Kit Manager
运维必备——ELK日志分析系统
Unforgettable Ali, 4 skills, 5 hr additional written tests, it's really difficult and sad to walk
OpenApi-Generator:简化RESTful API开发流程
VIM super practical guide collection of this one is enough
研究表明“气味相投”更易成为朋友
Browser node event loop
随机推荐
ADB basic commands
Unforgettable Ali, 4 skills, 5 hr additional written tests, it's really difficult and sad to walk
面渣逆袭:MySQL六十六问,两万字+五十图详解!有点六
Jerry's watch time synchronization [chapter]
2022零代码/低代码开发白皮书【伙伴云出品】附下载
JS iterator generator asynchronous code processing promise+ generator - > await/async
Everyone wants to eat a broken buffet. It's almost cold
文件的下载与图片的预览
二、帧模式 MPLS 操作
【蓝桥杯选拔赛真题43】Scratch航天飞行 少儿编程scratch蓝桥杯选拔赛真题讲解
numpy数组计算
(7) Web security | penetration testing | how does network security determine whether CND exists, and how to bypass CND to find the real IP
[opencv learning] [common image convolution kernel]
Unity SKFramework框架(十六)、Package Manager 开发工具包管理器
[opencv learning] [contour detection]
de4000h存储安装配置
嵌入式软件开发
Uniapp develops wechat applet Tencent map function and generates sig signature of location cloud
Ltc3307ahv meets EMI standard, step-down converter qca7005-al33 phy
linux下清理系统缓存并释放内存