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

倍增求LCA莫名WA,求助orz

Posted by garyhost at 2015-05-15 01:06:22 on Problem 1330 and last updated at 2015-05-15 01:06:54
```#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; i++)
#define REP(i, l, r) for (int i = l; i >= r; i--)
#define M 10
#define MAXN 50010

int n, fa[MAXN][M+5], root, dep[MAXN], N, first[MAXN], next[MAXN], T_T;
bool vis[MAXN];
struct tlist {int x, y;} a[MAXN];//数组模拟临接表

inline void add(int x, int y) {a[++N].x = x, a[N].y = y, next[N] = first[x], first[x] = N;}
inline void swap(int &a, int &b) {int t = a; a = b; b = t;}

inline void dfs(int x, int d) {//求每个节点的深度
vis[x] = 1;
dep[x] = d;
for (int i = first[x]; ~i; i = next[i])
if (!vis[a[i].y])
dfs(a[i].y, d+1);
}

inline void fuck() {rep(j, 1, M) rep(i, 1, n) fa[i][j] = fa[fa[i][j-1]][j-1];}//求i节点2^j祖先

inline int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);//保证depth(u) >= depth(v)
int deep = dep[u] - dep[v];
rep(i, 0, M) if ((1 << i) & deep) u = fa[u][i];//使u,v为同一层节点
if (u == v) return u;
REP(i, M, 0) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];//倍增
return fa[u][0];
}

int main() {
cin >> T_T;
while (T_T--) {
N = -1;
memset(fa, 0, sizeof(fa));
memset(first, -1, sizeof(first));
memset(next, -1, sizeof(next));
memset(dep, 0, sizeof(dep));
cin >> n;
int u, v;
rep(i, 1, n-1) {
scanf("%d%d", &u, &v);
fa[v][0] = u;//v的父节点为u
if (!fa[u][0]) root = u;
}
memset(vis, 0, sizeof(vis));
dfs(root, 1);
fuck();
scanf("%d%d", &u, &v);
printf("%d\n", LCA(u, v));
}

return 0;
}
```

Followed by: