poj 1330 LCA

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 using namespace std;
  8 const int MAXN=10010;
  9 int rmq[2*MAXN];//rmq数组，就是欧拉序列对应的深度序列
 10 struct ST
 11 {
 12     int mm[2*MAXN];
 13     int dp[2*MAXN][20];//最小值对应的下标
 14     void init(int n)
 15     {
 16         mm[0]=-1;
 17         for(int i=1;i<=n;i++)
 18         {
 19             mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
 20             dp[i][0]=i;
 21         }
 22         for(int j=1;j<=mm[n];j++)
 23         for(int i=1;i+(1<<j)-1<=n;i++)
 24         dp[i][j]=rmq[dp[i][j-1]]<rmq[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
 25     }
 26     int query(int a,int b)//查询[a,b]之间最小值的下标
 27     {
 28         if(a > b)swap(a,b);
 29         int k=mm[b-a+1];
 30         return rmq[dp[a][k]]<=rmq[dp[b-(1<<k)+1][k]]?dp[a][k]:dp[b-(1<<k)+1][k];
 31     }
 32 };
 33 //边的结构体定义
 34 struct Edge
 35 {
 36     int to,next;
 37 };
 38 Edge edge[MAXN*2];
 39 int tot,head[MAXN];
 40 int F[MAXN*2];//欧拉序列，就是dfs遍历的顺序，长度为2*n-1,下标从1开始
 41 int P[MAXN];//P[i]表示点i在F中第一次出现的位置
 42 int cnt;
 43 ST st;
 44 void init()
 45 {
 46     tot=0;
 47     memset(head,-1,sizeof(head));
 48 }
 49 void addedge(int u,int v)//加边，无向边需要加两次
 50 {
 51     edge[tot].to=v;
 52     edge[tot].next=head[u];
 53     head[u]=tot++;
 54 }
 55 void dfs(int u,int pre,int dep)
 56 {
 57     F[++cnt]=u;
 58     rmq[cnt]=dep;
 59     P[u]=cnt;
 60     for(int i=head[u];i!=-1;i=edge[i].next)
 61     {
 62         int v=edge[i].to;
 63         if(v==pre)continue;
 64         dfs(v,u,dep+1);
 65         F[++cnt]=u;
 66         rmq[cnt]=dep;
 67     }
 68 }
 69 void LCA_init(int root,int node_num)//查询LCA前的初始化
 70 {
 71     cnt=0;
 72     dfs(root,root,0);
 73     st.init(2*node_num-1);
 74 }
 75 int query_lca(int u,int v)//查询u,v的lca编号
 76 {
 77     return F[st.query(P[u],P[v])];
 78 }
 79 bool flag[MAXN];
 80 int main()
 81 {
 82     #ifndef ONLINE_JUDGE
 83     freopen("1.in","r",stdin);
 84     #endif
 85     int T;
 86     int N;
 87     int u,v;
 88     scanf("%d",&T);
 89     while(T--)
 90     {
 91         scanf("%d",&N);
 92         init();
 93         memset(flag,false,sizeof(flag));
 94         for(int i=1;i<N;i++)
 95         {
 96             scanf("%d%d",&u,&v);
 97             addedge(u,v);
 98             addedge(v,u);
 99             flag[v]=true;
100         }
101         int root;
102         for(int i=1;i<=N;i++)
103         if(!flag[i])
104         {
105             root=i;
106             break;
107         }
108         LCA_init(root,N);
109         scanf("%d%d",&u,&v);
110         printf("%d
",query_lca(u,v));
111     }
112     return 0;
113 }