当前位置:网站首页>Recent public ancestor (LCA) online practices
Recent public ancestor (LCA) online practices
2022-07-01 22:30:00 【Zqchang】
Catalog
The ancestors
In a rooted tree , The points passed by are called ancestors , For general painting, we also make a point itself an ancestor , In this way, each point will have many ancestors , The recent common ancestor is , Give us two points , The nearest common ancestor to them is the nearest common ancestor , Pictured
If two points overlap , The recent public ancestor is itself
How to find
Upward marking method ( Not commonly used )
Start at a point , To the root node , In the process of traversal , Mark all the dots he passed , Then do the same from another point , When we first came to the marked point, it was the nearest common ancestor , This time complexity is O(n) Of
Multiply
First, preprocess each point to go up 2 k 2^k 2k Who is Bu's father .
fa[i][j] From i Start , Go up 2 j 2^j 2j All nodes that can be reached by step , 0 <= j <= logn( With 2 Bottom )
Preprocess in a recursive way
Pictured , That is to say, from i This point starts , Go up 2 j 2^j 2j Step , Point after , Next, there are two situations , The first is j=0, The answer is i Parent node , When j>0 When , It's divided into two steps , First jump to 2 j − 1 2^{j - 1} 2j−1, Then jump back from this point 2 j − 1 2^{j - 1} 2j−1 Step , Just like the picture
depth[] Expressing depth , The specified root node depth is 1, Then the depth of the sub node of the root node is 2, The sub node depth is 3, And so on , Is the distance to the root node +1
Both arrays can be used dfs perhaps bfs Come and ask for
distance
seek xy The common ancestor of these two points , A two-step
1. First jump the two points to the same floor , In fact, let the deeper point jump to the same level as the shallower point , Here is the x Jump to and y Same floor
Based on the idea of a binary patchwork , For example, it has been pretreated 2 Of k Number to the power , Want to come up with t, Just take a look t The binary representation of , Then gather together , Just look directly from small to large , as long as t Greater than 2 The current order of , Just explain t Is to include this one , Then compare while reducing
then , Applied to the lca It's inside ,x To jump to y, What needs to jump is depth[y] - depth[x] Step , Then it has been pretreated f[i][j] Just enumerate from large to small , It's good to round up this number. In fact, you don't have to round up this number , Only need to enumerate , As long as meet
This condition can jump up
2. Let the two points jump up at the same time ( If the same point is reached after the first step , You can just end , There is no need for the second step ), Until both are the next level of common ancestors , The reason why we don't jump directly to the public ancestor is for the convenience of judgment
If f[a][k] = f[b][k] Words , We can only say f[a][k] and f[b][k] yes a and b A common ancestor of , It can't be said to be the recent public ancestor , But if f[a][k] != f[b][k] Words , Means f[a][k] = f[b][k] Not yet on the common ancestor , Because of this , Let's jump to the next point of the common ancestor , If equal , It is impossible to judge whether this point is the nearest public ancestor , Because it may also be the upper point of the nearest common ancestor , This cannot be judged
When jumping, it is also based on the idea of binary patchwork , Enumerate from big to small k, In the process of enumeration , As long as we jump 2 K 2^K 2K After step f[a][k] != f[b][k], It means they haven't jumped to their proper position , Just haven't jumped to the nearest public ancestor , You can let them jump up together once , until k Enumerate until , After enumeration x and y Even if we go to the next level of public ancestors , Now , Their common ancestor should be from x perhaps y Jump up one step
The time complexity of these two steps is logn, The preprocessing time complexity is nlogn Of , This multiplication requires lca Is also the most commonly used way
In the actual process , There will also be sentinels
be based on RMQ How to do it
First, put the whole tree dfs Go through it , Record in the process of traversal dfs Sequence , The time of recording here is every time we traverse , Whether it is backtracking or the first traversal, you should record , The following is an example
dfs The sequence should be
Here or here x and y Distance between , That's a 8 One 5, Any one 8 One 5 Fine , Then it turns into the interval minimum problem , You can use it RMQ Or segment tree
Example
The board question is not explained
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 40010;
vector<int> v[N];
int depth[N], fa[N][16];
queue<int> q;
int root, n, m;
void bfs()
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0; depth[root] = 1;
q.push(root);
while(q.size())
{
int t = q.front();
q.pop();
for(auto i : v[t])
{
if(depth[i] > depth[t] + 1)
{
depth[i] = depth[t] + 1;
q.push(i);
fa[i][0] = t;
for(int j=1; j<=15; j ++)
{
fa[i][j] = fa[fa[i][j - 1]][j - 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(fa[a][i] != fa[b][i])
{
a = fa[a][i];
b = fa[b][i];
}
return fa[a][0];
}
signed main()
{
fast;
cin >> n;
int a, b;
for(int i=1; i<=n; i++)
{
cin >> a >> b;
if(b == -1) root = a;
else
{
v[a].push_back(b);
v[b].push_back(a);
}
}
bfs();
cin >> m;
while(m --)
{
cin >> a >> b;
int p = lca(a, b);
if(p == a) puts("1");
else if(p == b) puts("2");
else puts("0");
}
return 0;
}
边栏推荐
- 上半年暂停考试要补考?包含监理工程师、建筑师等十项考试
- Design and practice of new generation cloud native database
- Aidl basic use
- Talking from mlperf: how to lead the next wave of AI accelerator
- 基于K-means的用户画像聚类模型
- 比较版本号[双指针截取自己想要的字串]
- Pytest collection (2) - pytest operation mode
- 基础—io密集型计算和cpu密集型计算
- Copy ‘XXXX‘ to effectively final temp variable
- Show member variables and methods in classes in idea
猜你喜欢
Do you want to make up for the suspended examination in the first half of the year? Including ten examinations for supervision engineers, architects, etc
Microsoft, Columbia University | Godel: large scale pre training of goal oriented dialogue
Copy ‘XXXX‘ to effectively final temp variable
What is the difference between PMP and NPDP?
locust 系列入门
[noip2013] building block competition [noip2018] road laying greed / difference
业务可视化-让你的流程图'Run'起来
【juc学习之路第9天】屏障衍生工具
EasyExcel 复杂数据导出
K-means based user portrait clustering model
随机推荐
AirServer手机第三方投屏电脑软件
收到一封CTO来信,邀约面试机器学习工程师
Little p weekly Vol.11
地图其他篇总目录
完全注解的ssm框架搭建
比较版本号[双指针截取自己想要的字串]
Can I choose to open an account for stock trading on flush? Is it safe?
手动实现function isInstanceOf(child,Parent)
Sonic云真机学习总结6 - 1.4.1服务端、agent端部署
pytest合集(2)— pytest運行方式
【MySQL】explain的基本使用以及各列的作用
Make a three digit number of all daffodils "recommended collection"
BlocProvider 为什么感觉和 Provider 很相似?
Training on the device with MIT | 256Kb memory
多种智能指针
【深度学习】利用深度学习监控女朋友的微信聊天?
Medium pen test questions: flip the string, such as ABCD, print out DCBA
基于K-means的用户画像聚类模型
Copy ‘XXXX‘ to effectively final temp variable
News classification based on LSTM model