LCA(Least Common Ancestors)

#include<iostream>
#include<math.h>
#include<string.h>
#define MAXN 10005
using namespace std;
int head[MAXN*2],cnt;
struct edge {
  int to;
  int next;
} e[MAXN*2];//链式向前星的边
int N,d[MAXN],f[MAXN][30],n;
//N是最远跳2的多少次，d[]是每个点的深度，f[i][j]是i点的2^j祖先,n是有多少点
void init() {
  N=(int)(log(n)/log(2));
  cnt=0;
  for(int i=0; i<MAXN; i++) {
    head[i]=-1;
  }
  memset(f,0,sizeof(f));
}
void add(int u,int v) { //链式向前星
  e[cnt].to=v;
  e[cnt].next=head[u];
  head[u]=cnt++;
}
void dfs(int u,int fa,int dep) {
  d[u]=dep;//深度
  f[u][0]=fa;
  for(int i=1; i<=N; i++) {
    f[u][i]=f[f[u][i-1]][i-1];
  }//更新u点到root路径上的祖先
  for(int i=head[u]; i!=-1; i=e[i].next) {
    int v=e[i].to;
    if(v==fa)continue;//以防万一
    dfs(v,u,dep+1);
  }
}//用来求每个点的深度，和f[][]
int lca(int a,int b) {
  if(d[a]>d[b]) {
    swap(a,b);//b为深
  }
  for(int i=N; i>=0; i--) {
    if(d[f[b][i]]>=d[a]) {
      b=f[b][i];
    }
  }//b和a一样深
  if(a==b)return a;//a,b同链
  for(int i=N; i>=0; i--) {
    if( f[a][i] != f[b][i]) { //不相同就跳
      a=f[a][i];
      b=f[b][i];
    }
  }
  return f[a][0];//lca就是父节点
}
int main() {
  int t;
  cin>>t;
  while(t--) {
    cin>>n;
    init();
    for(int i=1; i<n; i++) {
      int a,b;
      cin>>a>>b;
      add(a,b);
      f[b][0]=a;//b的父是a
    }
    for(int i=1; i<n; i++) {
      if(f[i][0]==0) {
        dfs(i,0,1);//找到根结点
        break;
      }
    }
    int a,b;
    cin>>a>>b;
    cout<<lca(a,b)<<endl;
  }
}

#include<iostream>
#include<math.h>
#include<string.h>
#define MAXN 10005
using namespace std;
int head[MAXN*2],cnt;
bool vis[MAXN];//判断是否访问过了 
bool is_root[MAXN];//从根结点开始dfs 
int f[MAXN];//并查集f[] 
int sox,soy,ans;
struct edge {
  int to;
  int next;
} e[MAXN*2];
void add(int u,int v) { //链式向前星
  e[cnt].to=v;
  e[cnt].next=head[u];
  head[u]=cnt++;
}
void init() {
  cnt=0;
  for(int i=0; i<MAXN; i++) {
    head[i]=-1;
    f[i]=i;
  }
  memset(vis,false,sizeof(vis));
  memset(is_root,true,sizeof(is_root));
}
int find(int x) { //查询祖先节点
  if(x!=f[x])
    f[x]=find(f[x]);
  return f[x];
}
void join(int x,int y) { //合并小子树 
  int fx=find(x),fy=find(y);
  if(fx!=fy)
    f[fy]=fx;
}
void lca(int u){
  for(int i=head[u]; i!=-1; i=e[i].next) {
    int v=e[i].to;
    lca(v);
    join(u,v);
    vis[v]=true;
  }
  if(sox==u &&vis[soy] ){ //子树的父节点就是LCA 
    ans=find(soy);
  }
  if(soy==u &&vis[sox] ){
    ans=find(sox);
  }
}
int main() {
  int t;
  cin>>t;
  while(t--) {
    init();
    int n;
    cin>>n;
    for(int i=1; i<n; i++) {
      int a,b;
      cin>>a>>b;
      add(a,b);
      is_root[b]=false;
    }
    int root;
    for(int i=1; i<=n; i++){
      if(is_root[i]==true)
        root=i;
    }
    cin>>sox>>soy;
    lca(root);
    cout<<ans<<endl;
  }
}