「LCA」SP14932 LCA

LCA - Lowest Common Ancestor

原题链接LCA

题目大意

给出两个点，求LCA，多组输入输出

题目题解

..模板题，没什么好说的，多组输入输出 需要注意一下

//#define fre yes

#include <cstdio>
#include <cstring>
#include <iostream>

const int N = 1005;
int head[N << 1], ver[N << 1], to[N << 1];
int depth[N], f[N][22], lg[N];
bool Vis[N];

int tot;
void addedge(int x, int y) {
	ver[tot] = y;
	to[tot] = head[x];
	head[x] = tot++;
}

void dfs(int x, int fa) {
	depth[x] = depth[fa] + 1;
	f[x][0] = fa;
	for (int i = 1; (1 << i) <= depth[x]; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	
	for (int i = head[x]; ~i; i = to[i]) {
		int v = ver[i];
		if(v != fa) {
			dfs(v, x);
		}
	}
}

int lca(int x, int y) {
	if(depth[x] < depth[y]) {
		std::swap(x, y);
	}
	
	while(depth[x] > depth[y]) {
		x = f[x][lg[depth[x] - depth[y]] - 1];	
	}
	
	if(x == y) return x;
	
	for (int k = lg[depth[x]] - 1; k >= 0; k--) {
		if(f[x][k] != f[y][k]) {
			x = f[x][k];
			y = f[y][k];
		}
	} return f[x][0];
}

int tnt = 0;
int main() {
	static int T, n, m;
	scanf("%d", &T);
	while(T--) {
		memset(head, -1, sizeof(head));
		memset(depth, 0, sizeof(depth));
		memset(Vis, 0, sizeof(Vis));
		memset(f, 0, sizeof(f));
		tot = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			int k;
			scanf("%d", &k);
			for (int j = 1; j <= k; j++) {
				int x;
				scanf("%d", &x);
				addedge(i, x);
				addedge(x, i);
				Vis[x] = 1;
			}
		}
		
		int root = 0;
		for (int i = 1; i <= n; i++) {
			if(!Vis[i]) {
				root = i;
				break;
			}
		}
		
		dfs(root, -1);
		for (int i = 1; i <= n; i++) {
			lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
		}
		
		printf("Case %d:
", ++tnt);
		scanf("%d", &m);
		for (int i = 1; i <= m; i++) {
			int u, v;
			scanf("%d %d", &u, &v);
			printf("%d
", lca(u, v));
		}
	} return 0;
}