Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

倍增求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;
	    add(u, v), add(v, 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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator