LCA 예제 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef pair<double, double> pdd;

//변수 선언
vector<int> v[100006];
int parent[100006];
int depth[100006];
bool visited[100006];
int table[100006][17]; //log2(100000)=16.6xx...

void find_p(int cur, int par, int dep){ //트리의 깊이, 부모정보를 저장하는 함수
	visited[cur]=true;
	parent[cur]=par;
	depth[cur]=dep;
	for(int i=0;i<v[cur].size();i++){
		if(!visited[v[cur][i]])
			find_p(v[cur][i], cur, dep+1);
	}
}

int main() {	
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//문제 링크: https://www.acmicpc.net/problem/11438
	int n; cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b; cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	find_p(1, 0, 1);

	for(int i=1;i<=n;i++) table[i][0]=parent[i];
		for(int j=1;j<17;j++){
			for(int i=1;i<=n;i++){
				table[i][j]=table[table[i][j-1]][j-1];
			}
		}

	int m; cin>>m; //쿼리 갯수 
	while(m--){
		int a,b; cin>>a>>b;
		if(depth[a]<depth[b]) swap(a,b);
		int dis=depth[a]-depth[b];
		for(int i=log2(dis);i>=0;i--){
			if(dis&(1<<i)) a=table[a][i];
		} //깊이 맞춤
		if(a==b){ //a==b일 때
			cout<<a<<"\n";
			continue;
		}
		//a와 b가 다르고 a와 b가 같은 깊이에 존재한 노드인 상태
		dis=depth[a]-2;
		for(int i=16;i>=0;i--){
			if(table[a][i]!=table[b][i]){
				a=table[a][i];
				b=table[b][i];
			}
		}
		cout<<parent[a]<<"\n";
	}
	return 0;
}