【题目链接】
【算法】
倍增法求最近公共祖先
【代码】
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXN 10010 #define MAXLOG 20 struct Edge { int to,nxt; } e[MAXN]; int i,T,tot,n,root,x,y; int fa[MAXN],dep[MAXN],head[MAXN],anc[MAXN][MAXLOG]; template <typename T> inline void read(T &x) { int f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; } for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x/10); putchar(x%10+'0'); } template <typename T> inline void writeln(T x) { write(x); puts(""); } inline void add(int x,int y) { tot++; e[tot] = (Edge){y,head[x]}; head[x] = tot; } inline void lca_init(int u) { int i,v; anc[u][0] = fa[u]; for (i = 1; i < MAXLOG; i++) { if (dep[u] <= (i << 1)) break; anc[u][i] = anc[anc[u][i-1]][i-1]; } for (i = head[u]; i; i = e[i].nxt) { v = e[i].to; dep[v] = dep[u] + 1; lca_init(v); } } inline int lca(int u,int v) { int i,k; if (dep[u] > dep[v]) swap(u,v); k = dep[v] - dep[u]; for (i = 0; i < MAXLOG; i++) { if (k & (1 << i)) v = anc[v][i]; } if (u == v) return u; for (i = MAXLOG - 1; i >= 0; i--) { if (anc[u][i] != anc[v][i]) { u = anc[u][i]; v = anc[v][i]; } } return fa[u]; } int main() { read(T); while (T--) { memset(fa,0,sizeof(fa)); memset(anc,0,sizeof(anc)); read(n); tot = 0; for (i = 1; i <= n; i++) head[i] = 0; for (i = 1; i < n; i++) { read(x); read(y); add(x,y); fa[y] = x; } for (i = 1; i <= n; i++) { if (!fa[i]) root = i; } dep[root] = 1; lca_init(root); read(x); read(y); writeln(lca(x,y)); } return 0; }