#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<functional>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
#include<ctime>
#define pb push_back
#define pii pair<int,int>
#define LL __int64
#define INF 0x7fffffff
#define LLINF 0x7fffffffffffffff
using namespace std;
const int N = 10005;
int ver[N*2], R[N*2], first[N], vcnt;
bool vis[N];
struct eg{
    int u, v, nex;
    eg(){}
    eg(int a, int b, int c) { u = a, v = b, nex = c; }
}edg[N*2];
int fir[N*2], ecnt;
void add(int a, int b){
    edg[ecnt] = eg(a, b, fir[a]);
    fir[a] = ecnt++;
    edg[ecnt] = eg(b, a, fir[b]);
    fir[b] = ecnt++;
}
bool in[N];
void dfs(int u, int dep){
    vis[u] = 1, ver[++vcnt] = u, R[vcnt] = dep, first[u] = vcnt;
    for(int k = fir[u]; k != -1; k = edg[k].nex){
        int v = edg[k].v;
        if( !vis[v] ){
            dfs(v, dep+1);
            ver[++vcnt] = u, R[vcnt] = dep;
        }
    }
}
int dp[N*2][20];
void ST(int n){
    for(int i = 1; i <= n; ++i) dp[i][0] = i;
    for(int j = 1; (1<<j) <= n; ++j)
    for(int i = 1; i + (1<<j)-1 <= n; ++i){
        int a = dp[i][j-1], b = dp[i+(1<<j-1)][j-1];
        dp[i][j] = R[a] > R[b]? b : a;
    }
}
int query(int x, int y){
    int k = (int)(log(y-x+1.0)/log(2.0));
    int s1 = dp[x][k], s2 = dp[y-(1<<k)+1][k];
    return R[s1] > R[s2] ? s2 : s1;
}
int LCA(int u, int v){
    if(first[u] <= first[v])  return ver[query(first[u], first[v])];
    else return ver[query(first[v], first[u])];
}
int main(){
    int T, a, b;
    scanf("%d", &T);
    while( T-- ){
        int n;
        memset(fir, -1, sizeof(fir));
        memset(vis, 0, sizeof(vis));
        memset(in, 0, sizeof(in));
        ecnt = 0, vcnt = 0;
        scanf("%d", &n);
        for(int i = 1; i < n; ++i){
            scanf("%d %d", &a, &b);
            add(a, b);
            in[b] = 1;
        }
        int rt = 0;
        for(int i = 1; !rt && i <= n; ++i) if( !in[i] ) rt = i;
        dfs(rt, 1);
        ST(n*2-1);
        int u, v;
        scanf("%d %d", &u, &v);
        printf("%d\n", LCA(u,v));
    }
}

• Re:DFS序+ST表。 47ms (27) jskkk123 2015-08-08 15:33:16
  • Re:DFS序+ST表。 47ms (52) devilphoenix 2017-08-23 06:01:51