poj 1330

코드를 먼저 부착합니다.

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = (int)1e4+5;
int r[maxn];
int f[maxn];
int ansc[maxn];
int dgr[maxn];
bool visit[maxn];
vector<int> c[maxn];
vector<int> q[maxn];
int findf(int x){
	if(x != f[x]){
		f[x] = findf(f[x]);
	}
	return f[x];
}

int unify(int x,int y){
	int fx = findf(x);
	int fy = findf(y);
	if(fx == fy){
		return 0;
	}
	if(r[fx] < r[fy]){
		f[fx] = fy;
		r[fy] += r[fx];
	}
	else{
		f[fy] = fx;
		r[fx] += r[fy];
	}
	return 1;
}
int n;
void init(){
	for(int i = 0; i < n; ++i){
		r[i] = 1;
		f[i] = i;
		dgr[i] = 0;
		visit[i] = false;
		c[i].clear();
		q[i].clear();
		ansc[i] = 0;
	}
}
int LCA(int x){
	ansc[x] = x;
	int size = c[x].size();
	for(int i = 0; i < size; ++i){
		LCA(c[x][i]);
		unify(x,c[x][i]);
		ansc[findf(x)] = x;
	}
	visit[x] = true;
	size = q[x].size();
	for(int i = 0; i < size; ++i){
		if(visit[q[x][i]]){
			printf("%d
",ansc[findf(q[x][i])] + 1);
			return 0;
		}
	}
	return 0;
}

int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		init();
		int a, b;
		for(int i = 0; i < n - 1; ++i){
			scanf("%d%d",&a,&b);
			--a;
			--b;
			c[a].push_back(b);
			dgr[b]++;
		}
		scanf("%d%d",&a,&b);
		--a; --b;
		q[a].push_back(b);
		q[b].push_back(a);
		for(int i = 0; i < n; ++i){
			if(dgr[i] == 0){
				LCA(i);
				break;
			}
		}
	}
	return 0;
}

Tarjan은 트리에서 lca 문제를 해결하는 오프라인 알고리즘입니다.
깊이를 바탕으로 우선적으로 주유하고 모으다.