这么久了才做LCA的题，以前是感觉很难不敢去尝试，现在学习了一番之后发现算法本身并不难。。。。
学习时看了这篇博文：， 我觉得实现的过程最重要，就把博文中Tarjan算法实现的方法以及伪代码贴到下面：
Tarjan算法的基本思路：
1.任选一个点为根节点，从根节点开始。
2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。
3.若是v还有子节点，返回2，否则下一步。
4.合并v到u上。
5.寻找与当前点u有询问关系的点v。
6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。
遍历的话需要用到dfs来遍历，至于合并，最优化的方式就是利用并查集来合并两个节点。
下面上伪代码：
Tarjan(u)//marge和find为并查集合并函数和查找函数{ for each(u,v) //访问所有u子节点v { Tarjan(v); //继续往下遍历 marge(u,v); //合并v到u上 标记v被访问过; } for each(u,e) //访问所有和u有询问关系的e { 如果e被访问过; u,e的最近公共祖先为find(e); }}
算法的运用以及实现过程的举例，博文中讲的很详细，我想补充一下我对Tarjan算法的理解，
当程序在dfs过程中遍历到某个节点 N 时， 以 N 节点为根节点搜索它的子节点，在它的某一子节点或某一子树都遍历过后，遍历过的点的父节点都会变成节点 N。那么假设N的子树中 i 节点被遍历了，其父节点变成N ； 遍历到其他子节点 j 时， 若恰好存在询问 i , j ，且 i , j 都在以 N 为根的树内，那么就可以直接得到 i, j 的LCA为 N 节点。那么在一次dfs过程中就都得到了所有询问的LCA
以下是两道例题的AC代码：
CODEVS 2370 小机房的树
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int MAXN=75005; 7 struct Edge{ 8 int to; 9 int cost;10 int id;11 };12 vector vec[MAXN];13 vector Q[MAXN];14 bool vis[MAXN];15 int p[MAXN], res[MAXN];16 long long d[MAXN], resd[MAXN];17 void add_edge(int u, int v, int c){18 vec[u].push_back((Edge){v, c, -1});19 vec[v].push_back((Edge){u, c, -1});20 }21 void add_query(int a, int b, int id){22 Q[a].push_back((Edge){b, 0, id});23 Q[b].push_back((Edge){a, 0, id});24 }25 int find(int x){26 return (p[x]==x)?x:(p[x]=find(p[x]));27 }28 void Union(int x, int y)29 {30 x=find(x);31 y=find(y);32 if(x==y) return;33 else p[x]=y;34 }35 void tarjan(int now, int fa)36 {37 for(int i=0;i
CODEVS 1036 商务旅行
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int MAXN=75005; 7 struct Edge{ 8 int to; 9 int cost;10 int id;11 };12 vector vec[MAXN];13 vector Q[MAXN];14 bool vis[MAXN];15 int p[MAXN], res[MAXN];16 long long d[MAXN], resd[MAXN];17 void add_edge(int u, int v, int c){18 vec[u].push_back((Edge){v, c, -1});19 vec[v].push_back((Edge){u, c, -1});20 }21 void add_query(int a, int b, int id){22 Q[a].push_back((Edge){b, 0, id});23 Q[b].push_back((Edge){a, 0, id});24 }25 int find(int x){26 return (p[x]==x)?x:(p[x]=find(p[x]));27 }28 void Union(int x, int y)29 {30 x=find(x);31 y=find(y);32 if(x==y) return;33 else p[x]=y;34 }35 void tarjan(int now, int fa)36 {37 for(int i=0;i