【LCA】最近の公的祖先を求める

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define maxn 10010

int point[maxn*2],next[maxn*2],last[maxn],tot,dep[maxn];
int fa[maxn][20],T,n,root,a,b;
bool flag[maxn];

     
void add(int x,int y){
     point[++tot]=y;
     next[tot]=last[x];
     last[x]=tot;
     }

void clear(){
      memset(flag,true,sizeof(flag));
      tot=0;
      memset(last,0,sizeof(last));
      }
      
void bfs(int root)
{
     queue<int>q;
     dep[root]=1;
     q.push(root);
     int i,j;
     while (!q.empty())
     {
         int tmp=q.front();
         q.pop();
         for (i=last[tmp];i;i=next[i])
         {
            int v=point[i];
            if (v==fa[tmp][0]) continue;
            dep[v]=dep[tmp]+1;
            fa[v][0]=tmp;
            q.push(v);
         }
         for (i=fa[tmp][0],j=0;i;i=fa[j][j++])
          fa[tmp][j+1]=fa[j][j];
     }
     
}        

int LCA(int u,int v)
{
     if (dep[u]<dep[v]) swap(u,v);
     int i;
     while (dep[u]>dep[v]){
        for (i=0;dep[fa[u][i]]>=dep[v];i++);
        u=fa[u][i-1];
        }
     while (u!=v){
           for (i=1;fa[u][i]!=fa[v][i];i++);
           u=fa[u][i-1];
           v=fa[v][i-1];
           }
     return u;
}
      
int main()
{ 
   scanf("%d",&T);
   while (T--){
      clear();
      scanf("%d",&n);
      for (int i=1;i<n;i++){
          scanf("%d%d",&a,&b);
          add(a,b);
          add(b,a);
          flag[b]=false;
          }
      for (int i=1;i<=n;i++)
         if (flag[i]){
            root=i;
            break;
            }
      bfs(root);
      int u,v;
      scanf("%d%d",&u,&v);
      printf("%d
",LCA(u,v));
    }
}