本篇博客总结一下LCA问题及其离线算法tarjan，并辅以模板以助记忆。
所谓LCA问题就是查询两个节点的最近公共祖先，tarjan算法利用深度优先检索和并查集来解决这一问题，对于所有的查询，可在一次dfs的过程中求解。
具体的tarjan算法看这篇博客，这位博主写得已经非常完备了：
最近公共祖先LCA(Tarjan算法)的思考和算法实现
看完了tarjan的工作过程再看一下它的代码实现：
poj 1330
Nearest Common Ancestors
我用这道题来展示一下LCA的模板：首先找到树的根，然后套用tarjan算法。至于为什么tarjan算法可行，上面那篇博文里没讲，我这里在注释中给出了粗略的证明，简单地说就是
在刚刚好访问完两个节点时，这两个节点的LCA必定没有
在DFS中回溯，正是因为没有回溯，使得find（v）可以定位到它。
#include <iostream>
#include <vector>
#include <fstream>
#define M 100009
using namespace std;
int f[M];
int root;
int degree_in[M];
bool vis[M];
vector<int> tree[M];
vector<int> query[M];
int find(int x)
{
return x == f[x] ? f[x] : f[x] = find(f[x]); //并查集的路径压缩操作
}
void tarjan(int u)
{
for (int i = 0; i < tree[u].size(); i++)//dfs
{
int v = tree[u][i];
tarjan(v);
f[v] = u; //v搜索完，将v合并到它父亲的集合u中
}
vis[u] = 1;
for (int i = 0; i < query[u].size(); i++)
{
int v = query[u][i];
if (vis[v]) //v被搜索过
{
cout << find(v) << endl; //寻找v所在的集合，即为最近公共祖先
}
/*证明：设lca为u和v的最近公共祖先，v和u必然分别在lca的两个不同的子树中(否则必然能找到更接近u、v的LCA)，根据dfs性质，
u还没有完成dfs,因此lca也没有完成dfs，f[lca]=lca依然成立,而v所在的子树搜索已经完成，因此其f已经全部更新，通过find函数一级级向上找，
最终由于f[lca] = lca而停止，证毕。*/
}
}
void init(int n)
{
for (int i = 0; i <= n; i++)
{
vis[i] = false;
tree[i].clear();
query[i].clear();
degree_in[i] = 0;
f[i] = i;
}
}
int main()
{
//fstream cin("test.txt");
int k;
cin >> k;
while (k--)
{
int n;
cin >> n;
init(n);
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
tree[a].push_back(b);
degree_in[b]++;
}
for (int i = 1; i <= n; i++)
{
if (degree_in[i] == 0)
root = i;
}
int a, b;
cin >> a >> b;
query[a].push_back(b);
query[b].push_back(a);
tarjan(root);
}
//system("pause");
return 0;
}
poj1986
Distance Queries
这道题复杂一点，其本身是一个无向带权图，可以当成树来做，不是让你直接求LCA，而是要两个点之前的距离。
用dis[]来表示到root的距离，则a、b之间的距离就等于dis[ a ] + dis[ b ] — 2*dis[ LCA(a,b) ]
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdio>
using namespace std;
struct node {
int num, dis; //dis(index for query)
node(int a, int b) :num(a), dis(b) {};
};
vector<node> tree[40005], query[40005];
int ans[10005];
int dis[40005];
int father[40005];
bool vis[40005];
int find(int x)
{
if (x != father[x])
father[x] = find(father[x]);
return father[x];
}
void tarjan(int u, int len)
{
dis[u] = len;
father[u] = u;
vis[u] = 1;
for (int i = 0; i < query[u].size(); i++)
{
int v = query[u][i].num;
if (vis[v])
{
int index = query[u][i].dis;
int lca = find(v);
ans[index] = dis[u] + dis[v] - 2 * dis[lca];
}
}
for (int i = 0; i < tree[u].size(); i++)
{
if (!vis[tree[u][i].num])
{
int v = tree[u][i].num;
int dis = tree[u][i].dis;
tarjan(v, len + dis);
father[v] = u;
}
}
}
int main()
{
//fstream cin("test.txt");
int n, m;
scanf("%d%d", &n, &m);
int a, b, dis;
char ch;
for (int i = 0; i < m; i++)
{
scanf("%d%d%d %c", &a, &b, &dis, &ch);
tree[a].push_back(node(b, dis));
tree[b].push_back(node(a, dis));
}
int q;
scanf("%d", &q);
for (int i = 0; i < q; i++)
{
scanf("%d%d", &a, &b);
query[a].push_back(node(b, i));
query[b].push_back(node(a, i));
}
tarjan(1, 0);
for (int i = 0; i < q; i++)
printf("%d\n", ans[i]);
//system("pause");
return 0;
}
