问题就是求x和y的最近公共祖先。
思路：把x到根节点的路径标记一下，然后去搜y到根节点的路径，碰到的第一个就是答案了。具体实现看代码：

#include <iostream>
#include <memory.h>
using namespace std;
const int maxn=10005;
int vis[maxn],p[maxn];
int main()
{
    int T,n,i,x,y;
    cin>>T;
    while(T--)
    {
        cin>>n;
        memset(vis,0,sizeof(vis));
        memset(p,0,sizeof(p));
        for(i=1;i<n;i++)
        {
            cin>>x>>y;
            p[y]=x;
        }
        cin>>x>>y;
        while(x){
            vis[x]=1;
            x=p[x];
        }
        while(y){
            if(vis[y]) break;
            y=p[y];
        }
        cout<<y<<endl;
    }
    return 0;
}

• Re:（其实就是 并查集），没有复杂的数据结构和算法哦~ (727) kn 2012-12-15 12:51:42