题目：http://poj.org/problem?id=1330
题意：给定一个有向树，求树中两点的LCA
思路：倍增法，留个模板。这个讲的不错点这里
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N = 10010; const int INF = 0x3f3f3f3f; struct edge { int to, next; }g[N*2]; int cnt, head[N]; int dep[N], p[N][31]; int n, in[N]; void add_edge(int v, int u) { g[cnt].to = u, g[cnt].next = head[v], head[v] = cnt++; } void dfs(int v, int fa) { for(int i = head[v]; i != -1; i = g[i].next) { int u = g[i].to; if(u == fa) continue; if(! dep[u]) dep[u] = dep[v] + 1, p[u][0] = v, dfs(u, v); } } void init() { for(int j = 1; (1<<j) <= n; j++) for(int i = 1; i <= n; i++) p[i][j] = p[p[i][j-1]][j-1]; } int LCA(int v, int u) { if(dep[v] < dep[u]) swap(v, u); int d = dep[v] - dep[u]; for(int i = 0; (d>>i) != 0; i++) if((d>>i) & 1) v = p[v][i]; if(v == u) return v; for(int i = 20; i >= 0; i--) if(p[v][i] != p[u][i]) v = p[v][i], u = p[u][i]; return p[v][0]; } int main() { int t, a, b; scanf("%d", &t); while(t--) { scanf("%d", &n); cnt = 0; memset(head, -1, sizeof head); memset(in, 0, sizeof in); for(int i = 1; i < n; i++) scanf("%d%d", &a, &b), add_edge(a, b), in[b]++; memset(dep, 0, sizeof dep); int root; for(int i = 1; i <= n; i++) if(in[i] == 0) root = i; dep[root] = 1; dfs(root, -1); init(); scanf("%d%d", &a, &b); printf("%d\n", LCA(a, b)); } return 0; }