poj 1330 Nearest Common Ancestors (lca,用dfs+rmq在线求解)

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E4+7;
 7vector <int>edge[N];
 8int n;
 9int in[N];
10int cur;
11int E[2*N];
12int R[N];
13int depth[2*N];
14int dp[2*N][16];
15void dfs ( int u,int dep)
16{
17  //  cout<<"u:"<<u<<" dep:"<<dep<<endl;
18    cur++;
19    E[cur] = u;
20    depth[cur] = dep;
21    R[u] = cur;  //有向图存的话，在这里访问的一定是第一次经过。

 1    int siz = edge[u].size();
 2    for ( int i = 0 ; i < siz ; i++)
 3    {
 4	int v = edge[u][i];
 5	dfs(v,dep+1);
 6	cur++;  //返回时还经过一次。
 7	E[cur] = u ;
 8	depth[cur] = dep;
 9    }
10}

1int _min(int l,int r)
2{
3    if (depth[l]<depth[r]) return l;
4    return r;
5}

1void rmq_init()
2{
3    for ( int i =  1 ; i <= 2*n+2 ; i++) dp[i][0] = i;

1    for ( int j = 1 ;  (1<<j) <= 2*n+2 ; j++ )
2	for ( int i = 1; i + (1<<j)-1 <=2*n+2 ; i++)
3	    dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
4}

 1int rmq_min( int l,int r)
 2{
 3    if (l>r) swap(l,r);
 4    int k = 0 ;
 5    while (1<<(k+1)<=r-l+1) k++;
 6    return _min(dp[l][k],dp[r-(1<<k)+1][k]);
 7}
 8int main()
 9{
10	#ifndef  ONLINE_JUDGE 
11	freopen("code/in.txt","r",stdin);
12  #endif
13	int T;
14	cin>>T;
15	while (T--)
16	{
17	    scanf("%d",&n);
18	    ms(in,0);
19	    ms(E,0);
20	    ms(R,0);
21	    ms(depth,0);
22	    for ( int i = 1 ; i <= n ; i++) edge[i].clear();
23	    for ( int i = 1 ; i <= n-1 ; i++)
24	    {
25		int u,v;
26		scanf("%d %d",&u,&v);
27		edge[u].push_back(v);
28		in[v]++;
29	    }

1	    cur = 0 ;
2	    dfs(root,0);
3	    rmq_init();

1	    int x,y;
2	    scanf("%d %d",&x,&y);
3	    printf("%d\n",E[rmq_min(R[x],R[y])]);
4	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}