题意，一棵有N个结点的有根树，询问一次两个给定结点的最近公共祖先（T组测试数据，2<=N<=10,000）。
题目链接：http://poj.org/problem?id=1330
——>>LCS, LCP, 一直不知道还有个LCA（最近公共祖先）。。。
这题因为询问只有一次，只需用上简单实现的LCA，不需用上离线的Tarjan这把牛刀。。。
1.求出各结点的深度；
2.让询问的两结点的深度达到相同（深度大的往根方向升）；
3.此时再让两结点一起往上移，一直到相遇，相遇点即为所求点。
#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int maxn = 10000 + 10;int T, N, root;
int head[maxn], nxt[maxn], v[maxn], ecnt;
int fa[maxn], dep[maxn];void init(){ //初始化邻接表memset(head, -1, sizeof(head));ecnt = 0;
}void addEdge(int uu, int vv){ //邻接表加边v[ecnt] = vv;nxt[ecnt] = head[uu];head[uu] = ecnt;ecnt++;
}void read(){ //读入scanf("%d", &N);memset(fa, -1, sizeof(fa));int uu, vv;for(int i = 1; i < N; i++){scanf("%d%d", &uu, &vv);addEdge(uu, vv);fa[vv] = uu;}
}void bfs(){ //求出根结点及各结点的深度for(root = 1; root <= N && fa[root] != -1; root++);dep[root] = 1;queue<int> qu;qu.push(root);while(!qu.empty()){int x = qu.front(); qu.pop();for(int e = head[x]; e != -1; e = nxt[e]){dep[v[e]] = dep[x] + 1;qu.push(v[e]);}}
}int LCA(int a, int b){ //求结点a与结点b的最近公共祖先(LCA)if(dep[a] < dep[b]) swap(a, b); //先让结点a的深度为较大者while(dep[a] != dep[b]) a = fa[a]; //再把结点a的深度提升到结点b的深度，这时两结点的深度就相同了while(a != b){ //两结点一起往上移，一直到相遇（即原a,b的LCA）a = fa[a];b = fa[b];}return a;
}void solve(){int a, b;scanf("%d%d", &a, &b);printf("%d\n", LCA(a, b));
}int main()
{scanf("%d", &T);while(T--){init();read();bfs();solve();}return 0;
}再写了一个Tarjan算法的（利用dfs，如果正在访问的结点是询问的结点之一，同时另一个询问点已访问，那么它们的LCA就是另一个询问点的根结点）：
#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int maxn = 10000 + 10;int T, N, root;
int head[maxn], nxt[maxn], v[maxn], ecnt; //邻接表用
int pa[maxn], fa[maxn]; //pa[i]表示原树中结点i的你结点，fa[i]表示并查集中结点i的父结点
bool vis[maxn], ok; //LCA用void init(){memset(pa, -1, sizeof(pa)); //找根用memset(head, -1, sizeof(head)); //初始化邻接表ecnt = 0;memset(vis, 0, sizeof(vis)); //LCA用ok = 0;
}void addEdge(int uu, int vv){ //邻接表加边v[ecnt] = vv;nxt[ecnt] = head[uu];head[uu] = ecnt;ecnt++;
}int Find(int x){return x == fa[x] ? x : (fa[x] = Find(fa[x]));
}void LCA(int x, int a, int b){ //在x及其子树中，求结点a与结点b的最近公共祖先(LCA)if(ok) return;fa[x] = x;for(int e = head[x]; e != -1; e = nxt[e]){LCA(v[e], a, b);fa[v[e]] = x;}vis[x] = 1;if(x == a && vis[b]){ //题目只有一个询问，所以，判断一下就好了ok = 1;printf("%d\n", Find(b));return;}else if(x == b && vis[a]){ok = 1;printf("%d\n", Find(a));return;}
}void read(){ //读入scanf("%d", &N);int uu, vv;for(int i = 1; i < N; i++){scanf("%d%d", &uu, &vv);addEdge(uu, vv);pa[vv] = uu;}
}void solve(){for(root = 1; pa[root] != -1; root++); //找根int a, b;scanf("%d%d", &a, &b);LCA(root, a, b);
}int main()
{scanf("%d", &T);while(T--){init();read();solve();}return 0;
}