LCA问题算是一类比较经典的树上的问题
做法比较多样
比如说暴力啊，倍增啊等等
今天在这里给大家讲一下tarjan算法！
tarjan求LCA是一种稳定高速的算法
时间复杂度能做到预处理O(n + m)，查询O(1)
它的主要思想是dfs和并查集
1.输入数据，找出根节点(或输入的)并将图存起来
2.输入需要查找的每一对点(两个点)，也存起来(也存成图)
3.从根节点开始向它的每一个孩子节点进行深搜
4.同时开一个bool类型的数组记录此节点是否搜索过
5.搜索到p节点时先将p标记为已经搜索过了
6.然后遍历所有与p相连的节点，并标记为已经搜索过了
7.接着将p的子节点和p合并(此处要用到并查集)
8.然后遍历所有和p有询问关系的p的子节点
9.若该子节点已经遍历过，则一定可以将该子节点和p的父亲节点合并
可能还是有很多人并没有完全理解这段文字叙述的算法过程
下面就直接上代码(注释很详细)
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<string> #include<iostream> #include<algorithm> #include<map> #include<set> #include<queue> #include<stack> #include<vector> using namespace std; typedef long long ll; const int maxn = 5e5 + 5; int read() { int ans = 0, op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct Drug { int next, to, lca; }edge[maxn<<1], qedge[maxn<<1];//edge[N]为树的链表;qedge[N]为需要查询LCA的两节点的链表 int n, m, s, x, y; int num_edge, num_qedge, head[maxn], qhead[maxn], father[maxn]; bool visit[maxn];//判断是否被找过 void add_edge(int from, int to)//建立树的链表 { edge[++num_edge].next = head[from]; edge[num_edge].to = to; head[from] = num_edge; // printf("#%d #%d #%d #%d ", num_edge, head[from], from, edge[num_edge].next); } void add_qedge(int from, int to)//建立需要查询LCA的两节点的链表 { qedge[++num_qedge].next = qhead[from]; qedge[num_qedge].to = to; qhead[from] = num_qedge; } int find(int x)//找爹函数 { if(father[x] ^ x) father[x] = find(father[x]); return father[x]; } void dfs(int x)//把整棵树的一部分看作以节点x为根节点的小树, x的初始值为s； { father[x] = x;//由于节点x被看作是根节点，所以把x的father设为它自己 visit[x] = 1;//标记为已被搜索过 for(int k = head[x]; k ; k=edge[k].next)//遍历所有与x相连的节点 { if(!visit[edge[k].to])//若未被搜索 { dfs(edge[k].to);//以该节点为根节点搞小树 father[edge[k].to] = x;//把x的孩子节点的father重新设为x } } for(int k = qhead[x]; k ; k = qedge[k].next)//搜索包含节点x的所有询问 { if(visit[qedge[k].to])//如果另一节点已被搜索过 { qedge[k].lca = find(qedge[k].to); //把另一节点的祖先设为这两个节点的最近公共祖先 if(k & 1) qedge[k + 1].lca = qedge[k].lca; //由于将每一组查询变为两组，所以2n-1和2n的结果是一样的 else qedge[k - 1].lca = qedge[k].lca; } } } int main(){ n = read(), m = read(), s = read();//输入节点数，查询数和根节点 for(int i = 1;i < n;i++) { x = read(), y = read();//输入每条边 add_edge(x, y); add_edge(y, x); } for(int i = 1;i <= m;i++) { x = read(), y = read(); //输入每次查询，考虑(u,v)时若查找到u但v未被查找，所以将(u,v)(v,u)全部记录 add_qedge(x, y); add_qedge(y, x); } dfs(s); for(int i = 1;i <= m;i++) printf("%d ", qedge[i << 1].lca);//两者结果一样，只输出一组即可 // printf("%d", num_edge); return 0; }