BOJ 15480(LCA와 쿼리)풀이

이미지를 누르면 문제로 이동합니다

문제에 쓰여있는 그대로 R를 루트노드라고 하고 LCA(U, V)를 구해주면 끝인 문제이다. 이 문제를 처음 봤을 때 LCA의 sparse table를 입력마다 갱신하는 방법이 바로 떠오르겠지만 그럴 경우 코드를 작성하지 않아도 안된다는 것을 알 수 있다. 그럼 어떻게 해야 할까

 

이 그림은 위 문제의 테스트케이스를 그래프로 나타낸 것이다.

이때 (U, V)에 대해 R의 위치는 

 

1. R 이 LCA(U, V) 보다 위에 있을 때,

2. R 이 V -> LCA(U, V) 사이에 있는 노드와 연결되어 있을 때,

3. R 이 U -> LCA(U,V) 사이에 있는 노드와 연결되어있을 때,

4. R이 루트 노드를 거쳐 U, V를 가야 할 때

 

이렇게 총 4개가 나오게 된다.

그럼 처음부터 따져보자.

 

노란색은 R(1), 빨간색은 U(2), V(4)

위 그림은 1번 경우에 대한 그림인데, 이런 상태에선 당연히 R을 루트로 한 LCA(U, V)는 LCA(U,V) 그대로 일것이다. R 이 LCA(U,V) 부터 그 위로 있으면 루트를 변경해도 차이가 없다.

 

노란색은 R(1), 빨간색은 U(3), V(7)

위 그림은 2번 경우에 대한 그림인데, V -> LCA(U,V) 사이에 R이 있으므로 R이 루트 일 때는 LCA(U, V)가 R 되거나 R 이 다른 간선을 통해 연결되어 있을 때 LCA(V, R) 이 된다.

3번 같은 경우도 위와 같은 방식으로 생각하면 바로 알 수 있다.

 

마지막 4번 같은 경우도 1번 경우처럼 LCA를 벗어났기 때문에 어떤 노드가 R이 된다 하더라도 LCA 에는 변함이 없다.

그러므로 1번과 4번을 합친 다음 2,3번을 제외한 나머지는 모두 LCA 그대로 출력하게 해 줘도 무방하다.

 

이 경우들을 LCA를 3번 돌린 다음 앞에서 설명했던 방법으로 비교하면서 알맞은 값을 출력해 주면 된다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=18; // 2의 18승이 100,000 을 넘음
ll N,M;
ll parent[100000][MAX]; // i 의 2^k 번째 부모 
ll depth[100000]; // 깊이 
ll cost[100000];
vector<ll>adj[100000]; // 그래프 vector 

// dfs로 트리만들고 parent[i][0], depth 채움
void dfs(ll curr){
	for(int i=0;i<adj[curr].size();i++){
		ll next=adj[curr][i];
		if(depth[next]==-1){
			parent[next][0]=curr;// 2^0 = 1 이므로 자신의 부모를 나타냄 
			depth[next]=depth[curr]+1; // 부모의 깊이에서 +1 
			cost[next]=cost[curr]+adj[curr][i];
			dfs(next); 
		}
	}
}
ll lca(ll u,ll v){
	// depth[u] >= depth[v] 가 되도록 u,v 를 변경
	if(depth[u]<depth[v])swap(u,v);
	int diff = depth[u]-depth[v]; // 깊이를 같게 하기 위해서 차이를 구함
	
	// 11을 이진수로 나타냈을 때 1011 이 나오는데, 이진수를 구하는 과정을 역으로 해보면
	// 2^3 * 1 + 2^2 * 0 + 2^1 * 1 + 2^0 * 1 로 나타나기 때문에 각 자리의 숫자와 2^j 를 곱하면 11을 얻을 수 있게 됨 
	int j=0;
	while(diff!=0){
		if(diff%2==1)u=parent[u][j];
		diff/=2;
		j++;
	} 
	// u,v 가 일정 높이로 같아짐
	// u,v의 2^j 번째 부모 노드가 다를 때 일정 높이 만큼 이동
	if(u!=v){
		// 2^j 에서 j를 감소시키면서 찾아감 , 2^a개를 뛰어넘는다면 다음에는 2^a이상으로 넘어갈 수 없기 때문에 이를 이용하여 a를 줄여가며 최종적으로 같아짐 
		for(int j=MAX-1;j>=0;j--){
			if(parent[u][j]!=-1 && parent[u][j]!=parent[v][j]){
				u=parent[u][j];
				v=parent[v][j];
			}
		}
		// 위 과정을 다 거치면 lca 의 자식에 위치하게 되므로 한번 올려줌
		u=parent[u][0]; 
	} 
	return u;
	
}

// 0-base
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> N;
	for(int i=0;i<N-1;i++){
		ll u,v,w;
		cin >> u >> v;
		u--;
		v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	//reset
	for(int i=0;i<100000;i++){
		fill(parent[i],parent[i]+MAX,-1);
		depth[i]=-1;
		cost[i]=-1;
	}
	depth[0]=0;
	cost[0]=0;
	dfs(0);
	
	for(int j=0;j<MAX-1;j++){
		for(int i=1;i<N;i++){ // i=0 는 루트 노드라 안함 
			if(parent[i][j]!=-1){
				parent[i][j+1]=parent[parent[i][j]][j];
			}
		}
	}
	
	//parent 채우기
	cin >> M;
	for(int i=0;i<M;i++){
		ll u,v,q;
		cin >> q >> u >> v;
		u--;v--;q--;
		ll UR=lca(u,q), VR=lca(v,M),UV=lca(u,v);
		//cout << UR << ' ' << VR << ' ' << UV << "\n";
		if(UR==UV&&VR==UV){
			cout << VR+1 << "\n";
		}else if(VR==UV&&UR!=UV){
			cout << UR+1 << "\n";
		}else{
			cout << UV << "\n";
		}
		
	
	} 
		
}