题意：给出一棵树，再给出两个节点a、b，求离它们最近的公共祖先。
方法一：
先用vector存储某节点的子节点，fa数组存储某节点的父节点，最后找出fa[root]=0的根节点root。
之后求每个节点的“高度”，更节点的高度为1，每往下一层高度+1。
读取a和b后，先求出它们位于同一个高度的祖先：
1.若此祖先相同，则即为最近的公共祖先。
2.若不相同，则求各自的父节点，知道两者的父节点相同，即为最近的公共祖先。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector> using namespace std;
const int maxn=;
int n;
vector<int> son[maxn];
int depth[maxn]; //depth[i]表示节点i的“高度”，这里根节点高度为1，每往下一层高度+1
int fa[maxn]; //fa[i]表示i的父节点 void init(){
for(int i=;i<maxn;i++)
son[i].clear();
memset(depth,,sizeof(depth));
memset(fa,,sizeof(fa));
}
//求出每个节点的“高度”
void dealdepth(int u){
for(int i=;i<son[u].size();i++){
int v=son[u][i];
depth[v]=depth[u]+;
dealdepth(v);
}
return;
} int solve(int a,int b){
//depth[a]>depth[b]，表示b在a的上方，先求出a的与b在同一层的祖先
if(depth[a]>depth[b]){
while(depth[a]>depth[b])
a=fa[a];
if(a==b)
return a;
}
//depth[a]<depth[b]，表示a在b的上方，先求出b的与a在同一层的祖先
else if(depth[a]<depth[b]){
while(depth[a]<depth[b])
b=fa[b];
if(a==b)
return a;
}
//同时求祖先，直至相等
while(a!=b){
a=fa[a];
b=fa[b];
}
return a;
}
int main()
{
int t,a,b,root,u,v; //root:根节点
scanf("%d",&t);
while(t--){
init();
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
son[u].push_back(v);
fa[v]=u;
}
for(int i=;i<=n;i++){
if(fa[i]==){
root=i;
break;
}
}
depth[root]=;
dealdepth(root);
scanf("%d%d",&a,&b);
int ans=solve(a,b);
printf("%d\n",ans);
}
return ;
}
方法二：用Tarjan算法求
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <string>
#include <vector>
/*
Tarjan算法
*/
using namespace std;
const int maxn=;
int n,t,a,b; //a,b是要求公共祖先的两点
bool flag; //flag为true表明LCA已经求出了a,b的公共祖先，那么就不用继续往下求了
int vis[maxn]; //LCA标记哪些节点已被访问过
int indegree[maxn]; //记录每个节点的入度，用来找寻根节点
int head[maxn];
int tot;
int ans; struct Edge{
int to,next;
}edge[maxn]; void add(int u,int v){
edge[tot].next=head[u];
edge[tot].to=v;
head[u]=tot++;
}
//并查集
struct UF{
int fa[maxn];
void init(){
for(int i=;i<=n;i++)
fa[i]=i;
}
int find_root(int x){
if(fa[x]!=x)
fa[x]=find_root(fa[x]);
return fa[x];
}
void Union(int u,int v){
fa[v]=fa[u];
}
}uf; void LCA(int u){
if(flag)
return;
int v;
for(int k=head[u];k!=-;k=edge[k].next){
v=edge[k].to;
LCA(v);
uf.Union(u,v);
}
vis[u]=; //标记节点u
//看看u是否是查询的两个节点中的一个
if(u==a){
if(vis[b]){
ans=uf.fa[uf.find_root(b)];
flag=true;
}
}
else if(u==b){
if(vis[a]){
ans=uf.fa[uf.find_root(a)];
flag=true;
}
}
}
int main()
{
int root,u,v;
cin>>t;
while(t--){
memset(indegree,,sizeof(indegree));
memset(head,-,sizeof(head));
tot=;
cin>>n;
for(int i=;i<n;i++){
cin>>u>>v;
add(u,v);
indegree[v]++;
}
for(int i=;i<=n;i++){
if(!indegree[i]){
root=i;
break;
}
}
cin>>a>>b;
flag=false;
memset(vis,,sizeof(vis));
uf.init();//一开始忘记初始化了额
LCA(root);
cout<<ans<<endl; }
return ;
}