Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## DFS序+ST表。 47ms

Posted by kg20006 at 2015-06-14 21:26:21 on Problem 1330
```#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;
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);
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));
}
}
```

Followed by: