From Google Earth

Nearest Common Ancestors

其实就是LCA的模板题......屯一下板子

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct edge{
    int to;
    int next; 
};
edge es[maxn];
int head[maxn];
int cnt;
void add(int u,int v)
{
    es[cnt].to=v;
    es[cnt].next=head[u];
    head[u]=cnt++;
}
int in[maxn];
int fa[maxn];
void init(int n)
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int find_fa(int x)
{
    if(fa[x]!=x)    
        fa[x]=find_fa(fa[x]);
    return fa[x]; 
}
bool vis[maxn];
void join(int x,int y)
{
    int fx=find_fa(x);
    int fy=find_fa(y);
    if(fx!=fy){
        fa[fy]=fx;
    }
}
int ans;
int qx,qy;
void lca(int u)
{
    for(int i=head[u];i!=-1;i=es[i].next){
        int v=es[i].to;
        lca(v);
        join(u,v);
        vis[v]=1;
    }
    if(qx==u&&vis[qy])
        ans=find_fa(qy);
    if(qy==u&&vis[qx])
        ans=find_fa(qx);
}
int main()
{
    IOS;
    int t;cin>>t;
    while(t--){;
        mst(vis,0);
        mst(head,-1);mst(in,0);
        ans=0;
        int n;cin>>n;
        init(n);
        for(int i=0;i<n-1;i++){
            int u,v;
            cin>>u>>v;
            add(u,v);in[v]++;
        }
        int rt;
        for(int i=1;i<=n;i++){
            if(in[i]==0){
                rt=i;break;
            }
        }
        cin>>qx>>qy;
        lca(rt);
        cout<<ans<<endl;
    }
    return 0;
}