一般求lca的方式就是基于下面的模板,中间的过程就不推理了,有兴趣可以去听听y总的课,讲的很详细
模板题
给定一棵包含 n 个节点的有根无向树,节点编号互不相同,但不一定是 1∼n。
有 m 个询问,每个询问给出了一对节点的编号 x 和 y,询问 x 与 y 的祖孙关系。
输入格式
输入第一行包括一个整数 表示节点个数;
接下来 n 行每行一对整数 a 和 b,表示 a 和 b 之间有一条无向边。如果 b 是 −1,那么 aa 就是树的根;
第 n+2 行是一个整数 m 表示询问个数;
接下来 m 行,每行两个不同的正整数 x 和 y,表示一个询问。
输出格式
对于每一个询问,若 x 是 y 的祖先则输出 1,若 y 是 x 的祖先则输出 2,否则输出 0。
数据范围
1≤n,m≤4×10^4
1≤每个节点的编号≤4×10^4
输入样例:
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
输出样例:
1
0
0
0
2
代码
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int N = 4e4 + 10;
int dep[N];
int fa[N][16];
vector<int> e[N];
int n, m;
int x, y;
void bfs(int root){
memset(dep,0x3f,sizeof(dep));
queue<int> q;
q.push(root);
dep[0] = 0, dep[root] = 1;
while(!q.empty()){
auto t = q.front();
q.pop();
for(auto x : e[t]){
if(dep[t] + 1 < dep[x]){
dep[x] = dep[t] + 1;
fa[x][0] = t;
for(int i = 1;i <= 15;i ++){
fa[x][i] = fa[fa[x][i - 1]][i - 1];
}
q.push(x);
}
}
}
}
int lca(int a, int b){
if(dep[a] < dep[b]) swap(a, b);
for(int i = 15;i >= 0;i --){
if(dep[fa[a][i]] >= dep[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];
}
int main()
{
cin >> n;
int root = 0;
for(int i = 0,A,B;i < n;i ++){
cin >> A >> B;
if(B == -1) root = A;
else e[A].push_back(B), e[B].push_back(A);
}
bfs(root);
cin >> m;
while(m --){
cin >> x >> y;
if(lca(x,y) == x) cout << 1 << endl;
else if(lca(x,y) == y) cout << 2 << endl;
else cout << 0 << endl;
}
return 0;
}
这是用bfs初始化的模板,下面给出用dfs初始化的模板
1171.距离
给出 n 个点的一棵树,多次询问两点之间的最短距离。
注意:
- 边是无向的。
- 所有节点的编号是 1,2,…,n
输入格式
第一行为两个整数 n 和 m。n 表示点数,m 表示询问次数;
下来 n−1 行,每行三个整数 x,y,k,表示点 x 和点 y 之间存在一条边长度为 k;
再接下来 m 行,每行两个整数 x,y,表示询问点 x 到点 y 的最短距离。
树中结点编号从 1 到 n。
输出格式
共 m 行,对于每次询问,输出一行询问结果。
数据范围
2≤n≤10^4
1≤m≤2×10^4
0<k≤100
1≤x,y≤n
输入样例1:
2 2
1 2 100
1 2
2 1
输出样例1:
100
100
输入样例2:
3 2
1 2 10
3 1 15
1 2
3 2
输出样例2:
10
25
这题没有那么素,但是也很模板了,大致思路说下,一般来说两点最短路想到的会是dijkstra,但是这道题不适合,因为数据范围大,如果只查询一次那dijkstra非常合适。那么就要先预处理好所有点到根节点的距离,那么如果pa是a和b的最近公共祖先则a和b的最短距离就是dist[a]+dist[b] - 2*dist[pa]
代码
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e4 + 10;
int fa[N][16];
int dep[N], dist[N];
vector<PII> e[N];
int n, m;
void dfs(int u,int pa){
dep[u] = dep[pa] + 1;
fa[u][0] = pa;
for(int i = 1;i <= 14;i ++){
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for(auto [x, w] : e[u]){
if(x == pa) continue;
dist[x] = dist[u] + w;
dfs(x, u);
}
}
int lca(int a, int b){
if(a == b) return a;
if(dep[a] < dep[b]) swap(a, b);
for(int i = 14;i >= 0;i --){
if(dep[fa[a][i]] >= dep[b]){
a = fa[a][i];
}
}
if(a == b) return a;
for(int i = 14;i >= 0;i --){
if(fa[a][i] != fa[b][i]){
a = fa[a][i];
b = fa[b][i];
}
}
return fa[a][0];
}
int main()
{
cin >> n >> m;
for(int i = 0,u,v,w;i < n - 1;i ++){
cin >> u >> v >> w;
e[u].push_back({v,w}), e[v].push_back({u,w});
}
dep[0] = 0;
dfs(1, 0);
while(m --){
int a, b;
cin >> a >> b;
int pa = lca(a, b);
int dis = dist[a] + dist[b] - 2 * dist[pa];
cout << dis << endl;
}
return 0;
}
下面就是应用了
D. Paint the Tree(Lca + 树的直径)
378QAQ has a tree with nn vertices. Initially, all vertices are white.
There are two chess pieces called PAPA and PBPB on the tree. PAPA and PBPB are initially located on vertices aa and bb respectively. In one step, 378QAQ will do the following in order:
- Move PAPA to a neighboring vertex. If the target vertex is white, this vertex will be painted red.
- Move PBPB to a neighboring vertex. If the target vertex is colored in red, this vertex will be painted blue.
Initially, the vertex a is painted red. If a=b, the vertex a is painted blue instead. Note that both the chess pieces must be moved in each step. Two pieces can be on the same vertex at any given time.
378QAQ wants to know the minimum number of steps to paint all vertices blue.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤10^4). The description of the test cases follows.
The first line of each test case contains one integer n (1≤n≤2⋅10^5).
The second line of each test case contains two integers a and b (1≤a,b≤n).
Then n−1 lines follow, each line contains two integers xi and yi (1≤xi,yi≤n), indicating an edge between vertices xi and yi. It is guaranteed that these edges form a tree.
It is guaranteed that the sum of nn over all test cases does not exceed 2⋅10^5
Output
For each test case, output the minimum number of steps to paint all vertices blue.
题目大意
给出一棵树,每个点初始为白色。Alice 在 PA,Bob 在 PB。每次操作两人需要移动到相邻的结点,Alice 会将脚下的白点染成红色,Bob 会将脚下的红点染成蓝色。
求将整棵树染成蓝色的最小操作次数。
我个人认为一般跟树的直径相关的题,还是比较难的,至少代码是真的难写。不了解树的直径的可以看看 树与图的深度优先遍历(dfs的图论中的应用)_有向图深度优先遍历例题-CSDN博客
对于这个问题我们就假设么,最差情况是怎么样的,那就是 a 先涂一遍 n 步, b 在涂一遍 n 步。最差情况就是2 * n了,那么我们假设在a 还没涂完全图的时候他们相遇了, 剩下的步子只要 b 跟着 a 走了,就比如走了 x 步吧,那是不是就省了 x 步,b 第二遍涂的时候就可以不用去涂之前涂过的 x 个格子了。那就找到子问题了,求最大的 x
这里呢比较难想。主要还是对树的直径敏不敏感。肯定我们首先要让a 和 b先相遇么,这个很容易想到 Lca(pa) 但是相遇的点一定就是 pa 吗?能不能保证之后走的格子数最大,不行。应该把此路径当作树的直径然后找中心点,这样就一定保证之后走的最大,可以画图想想。那么还有一个问题如果路径数是偶数那说明他们不能同时到那个中心点,那么我们就先走 add 步,然后让他们的的下一个点是同一个点距离是1,然后再走一步就可以相遇了。然后把 add 加上把 x 减掉就行了
代码
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int dep[N];
int fa[N][22];
vector<int> e[N];
int t;
int n, A, B;
void dfs(int u,int pa){
dep[u] = dep[pa] + 1;
fa[u][0] = pa;
for(int i = 1;i <= 19;i ++){
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for(auto x : e[u]){
if(x == pa) continue;
dfs(x, u);
}
}
int lca(int a, int b){
if(a == b) return a;
if(dep[a] < dep[b]) swap(a, b);
for(int i = 19;i >= 0;i --){
if(dep[fa[a][i]] >= dep[b]){
a = fa[a][i];
}
}
if(a == b) return a;
for(int i = 19;i >= 0;i --){
if(fa[a][i] != fa[b][i]){
a = fa[a][i];
b = fa[b][i];
}
}
return fa[a][0];
}
void dfs1(int u,int pa){
dep[u] = dep[pa] + 1;
for(auto x : e[u]){
if(x == pa) continue;
dfs1(x, u);
}
}
void solve()
{
cin >> n >> A >> B;
for(int i = 1;i <= n;i ++){
e[i].clear(), dep[i] = 0;
for(int j = 0;j < 22;j ++){
fa[i][j] = 0;
}
}
for(int i = 0,x,y;i < n - 1;i ++){
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1, 0);
int pa = lca(A, B);
// cout << pa << endl;
vector<int> p1, p2;
int cur = A;
while(cur != pa){
p1.push_back(cur);
cur = fa[cur][0];
}
p1.push_back(pa);
cur = B;
while(cur != pa){
p2.push_back(cur);
cur = fa[cur][0];
}
for(int i = p2.size() - 1;i >= 0;i --) p1.push_back(p2[i]);
// for(int i = 0;i < p1.size();i ++) cout << p1[i] << " ";
// cout << endl;
int add = (p1.size() - 1) / 2 + (p1.size() % 2 == 0), center = p1[(p1.size() - 1) / 2];
// cout << add << " " << center << endl;
dfs1(center, 0);
int mx = -1;
for(int i = 1;i <= n;i ++) mx = max(mx, dep[i]);
cout << (n - 1) * 2 - mx + add + 1 << endl;
}
int main()
{
cin >> t;
while(t --){
solve();
}
return 0;
}
加油
标签:dep,fa,祖先,实用,int,pa,Lca,include,10 From: https://blog.csdn.net/AuRoRamth/article/details/143438855