1 /*Source Code 2 Problem: 1330        User: huifeidmeng 3 Memory: 1232K        Time: 63MS 4 Language: C++        Result: Accepted 5  6     Source Code 7 */ 8     #include<iostream> 9     #include<vector>10     #include<cstdio>11     #include<cstring>12     #include<cstdlib>13     using namespace std;14     const int maxn=10002;15     vector<int> tree[maxn],qus[maxn];16     int rank[maxn],father[maxn];17     bool vis[maxn];18     int rudu[maxn];19     int lroot[maxn];20     void init(int n){21          memset(vis,0,sizeof(vis));22          memset(rudu,0,sizeof(rudu));23          memset(lroot,0,sizeof(lroot));24         for(int i=1;i<=n;i++){25             father[i]=i;26             rank[i]=1;27             tree[i].clear();28             qus[i].clear();29         }30     }31     int find(int a){32        while(a!=father[a])33              a=father[a];34         return a;35     }36     void Union(int a,int b)37     {38         int x=find(a);39         int y=find(b);40         if(x==y) return ;41         if(rank[x]<rank[y]){42           rank[y]+=rank[x];43           father[x]=y;44         }45         else {46          rank[x]+=rank[y];47          father[y]=x;48         }49     }50     void LCA(int u)51     {52       lroot[u]=u;53       int len=tree[u].size();54       for(int i=0;i<len;i++){55           LCA(tree[u][i]);56           Union(u,tree[u][i]);57           lroot[find(u)]=u;58       }59       vis[u]=1;60       int ss=qus[u].size();61       for(int i=0;i<ss;i++){62             if(vis[qus[u][i]]){63                 printf("%d\n",lroot[find(qus[u][i])]);64                 return ;65             }66       }67     }68     int main()69     {70       int cas,n,u1,u2;71       //freopen("test.in","r",stdin);72       scanf("%d",&cas);73       while(cas--){74           scanf("%d",&n);75           init(n);76           for(int i=1;i<n;i++){77           scanf("%d%d",&u1,&u2);78           tree[u1].push_back(u2);79           rudu[u2]++;  80           }81           scanf("%d%d",&u1,&u2);82           qus[u1].push_back(u2);83           qus[u2].push_back(u1);84           for(int i=1;i<=n;i++){85          if(0==rudu[i]){ //找到root86            LCA(i);87            break;88           }89           }90       }91     return 0;92     }