BOJ 13512(트리와 쿼리 3) 풀이

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

 

이 문제는 설명자체는 간단한데, 트리가 주어지고 1번 쿼리는 트리의 노드를 바꾸는 거고, 2번 쿼리는 현재 만들어진 트리에서 1번 노드에서 v 노드로 가는 길에 1번 노드와 가장 가까운 검정 노드의 번호를 출력하는 문제이다.

 

이 문제도 여러 가지 풀이 방법이 있는 걸로 알고 있고

가장 대표적인 풀이가 HLD(Heavy heavy Light Decomposition)으로 알고 있는데,

그 풀이가 아닌 ETT(오일러 투어 테크닉) 와 lazy 세그 (느리게 갱신되는 세그먼트 트리), sparse table(희소 배열)을 이용한 풀이를 작성하겠다.

 

이 문제의 핵심은 2번 쿼리니 1번 쿼리는 2번쿼리의 구조 내에서 구현해 줘야 된다. 그러므로 2번 쿼리부터 설명하겠다.

 

1부터 v 로 가는 길에서 1에 가장 가까운 검정 노드를 구하려면 어떻게 해야 될까

이때 이분탐색의 개념을 사용한다.

 

이분 탐색은 반을 나누고, 그에 따라 왼쪽 또는 오른쪽 범위를 줄여나가는 알고리즘인데, 이런 알고리즘은 단순히 N 번 반복하는 것을 logN 번으로 줄여주는 좋은 알고리즘이다.

 

1부터 v로 가는 노드들 중 임의의 노드를 u라고 하겠다.

만약 내가 1에서 u 노드로 가는 길에 있는 노드들의 상태를 안다고 생각해 보자.

만약 그 안에 검정 노드가 있다면 당연히 u이후의 노드들은 절대 가장 가까운 검정 노드가 될 수 없을 것이다.

그러므로 기존에 1부터 v까지 탐색하던걸 1부터 u로 줄여서 탐색하면 된다.

 

이 방법을 이분탐색에서 반을 나눠서 구해줬던 방식을 예를 들어 적용해서 풀어보면

u는 1부터 v 사이의 중간에 위치해 있는 노드가 될 것이다. 그리고 우리는 1부터 u까지의 노드들의 상태를 알기 때문에 만약 검정 노드가 없다면 u 이후로, 검정 노드가 있다면 u 이전으로 탐색을 해주면 된다.

 

그럼 노드 상태를 어떻게 알 수 있을까

이때 우리는 세그먼트 트리를 이용한다.

검정을 1, 흰색을 0으로 두면 구간합을 구했을 때 0 보다 크다면 검정 노드가 있다는 걸 알 수 있다.

하지만 기존 세그 문제와는 다르게 여기서는 트리의 노드들의 세그의 노드가 돼서 범위를 잡기 어려운데, 이때 우리는 ETT(오일러 투어 테크닉)을 이용하면 범위를 쉽게 잡을 수 있다.

 

ETT는 dfs로 트리를 탐색하면서 순서대로 번호를 다시 매겨주는 방법인데, 이를 이용하면 기존 트리보다 범위를 잡는 것을 쉽게 할 수 있다.

 

이제 세그를 정의하겠다. 세그에 들어가는 값들을

 

1부터 u까지 지나오면서 검정의 개수

 

로 정의 해준다.

그러면 u의 값을 업데이트한다면, u 밑에 있는 자식 노드들에게 1을 더하거나 1을 빼주는 연산을 취해주면 된다.

또 u와 v 사이의 검은색 노드의 수를 구하는 방법도

(v가 u보다 깊은 위치에 있다고 할 때)

v까지의 검정 노드 개수 - u까지의 검정 노드 개수 + u의 상태를 계산해 주면 검은색 노드의 개수를 알 수 있게 된다.

 

다시 돌아와서 이제 검정 노드의 개수를 구하는 방법도 알았으니, 1과 v 사이에 중간에 위치하는 u 노드의 번호를 구해야 한다.

 

이는 sparse table(희소 배열, 스파스라고 부르겠음)을 이용하면 알 수 있는데,

 

스파스는 i 노드의 2^k 번째 부모를 저장하고 있는 배열이다.

이를 이용하면 k 가 작아지면서 v의 2^k 번째 부모 노드 값이 존재할 때, 검은색 노드 여부를 구해준다. 그리고 그에 따라 1 값을 2^k 번째 부모 노드로 변경해 주거나, v를 변경해 주는 과정을 거치면 된다.

LCA를 구할 때도 사용되지만 k를 거꾸로 하는 이유는 만약 v의 2^(k+1) 번째 부모 노드가 존재하지 않고, 2^k 번째 부모 노드가 존재할 때, 2^k번째의 노드의 2^k번째 부모 노드는 존재하지 않는다는 것을 알 수 있다.

(2^k 번째 부모 노드의 2^k번째 부모 노드는 v에게 2^(k+1) 번째 부모 노드와 같다. 수 1에서 배우는 거 생각해 보면 될 듯)

 

그러므로 k을 줄여나가면서 범위를 줄여나가면 되고, 당연하게도 2^k 가 N보다 작을 때부터 k가 성립되기 때문에 logN 이하의 적은 횟수로 탐색을 하게 된다.

 

이 과정들을 모두 합쳐서 구해주면 1번 노드에 가장 가까운 검정 노드를  구할 수 있게 되고 이를 출력해 주면 된다.

시간 복잡도는 O(MlogNlogN) 이 된다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=18; // 2의 18승이 100,000 을 넘음
struct nd{
	ll v,w;
};
struct st_ed{
	ll start,end;
};
ll N,M;
vector<st_ed>Q(100010);
ll parent[100010][MAX]; // i 의 2^k 번째 부모 
ll depth[100010]; // 깊이 
ll cost[100010];
ll node_number=0;
ll num_state[100010];
vector<nd>adj[100010]; // 그래프 vector 
vector<ll>seg(400000);
vector<ll>lazy(400000);

void segment(ll n,ll s,ll e){
	if(s==e){
		lazy[n]=0;
		seg[n]=0;
		return;
	}
	ll mid=(s+e)/2;
	segment(n*2,s,mid);
	segment(n*2+1,mid+1,e);
}
void propagate(ll n,ll s,ll e){
	if(lazy[n]!=0){
		seg[n]+=lazy[n]*(e-s+1);
		if(s!=e){
			lazy[n*2]+=lazy[n];
			lazy[n*2+1]+=lazy[n];
		}
		lazy[n]=0;
	}
}
void update(ll n,ll s,ll e,ll left,ll right,ll v){
	propagate(n,s,e);
	if(e<left||right<s)return;
	if(left<=s&&e<=right){
		lazy[n]+=v;
		propagate(n,s,e);
		return;
	}
	ll mid=(s+e)/2;
	update(n*2,s,mid,left,right,v);
	update(n*2+1,mid+1,e,left,right,v);
	seg[n]=seg[n*2]+seg[n*2+1];
}
ll SUM(ll n,ll s,ll e,ll left,ll right){
	propagate(n,s,e);
	if(e<left||right<s)return 0;
	if(left<=s&&e<=right){
		return seg[n];
	}
	ll mid=(s+e)/2;
	return SUM(n*2,s,mid,left,right)+SUM(n*2+1,mid+1,e,left,right);
}

// dfs로 트리만들고 parent[i][0], depth 채움
void dfs(ll curr){
	node_number++;
	Q[curr].start=node_number-1;
	for(int i=0;i<adj[curr].size();i++){
		ll next=adj[curr][i].v;
		if(depth[next]==-1){
			parent[next][0]=curr;// 2^0 = 1 이므로 자신의 부모를 나타냄 
			depth[next]=depth[curr]+1; // 부모의 깊이에서 +1 
			cost[next]=cost[curr]+adj[curr][i].w;
			dfs(next); 
		}
	}
	Q[curr].end=node_number-1;
}
ll query(ll u){
	ll v=0;
	if(SUM(1,0,N,0,N)==0)return -1;

	ll j=0;
	ll next=0;
	if(u!=v){
		/*
		next=Q[parent[v][j]].start;
		ans+=SUM(1,0,N,Q[v].start,Q[v].start)-SUM(1,0,N,next,next);
		v=parent[v][j];

		for(int j=MAX-1;j>=0;j--){
			if(u==v){
				if(num_state[u]==0)return -1;
				else return u+1;
			}
			if(parent[v][j]==-1)continue;
			else{
				ll next=parent[v][j];
				//cout << v <<' ' << next << ' ' << u << ' ' << SUM(1,0,N,next,next)-SUM(1,0,N,u,u)+num_state[u] << "\n";
				if(SUM(1,0,N,Q[next].start,Q[next].start)-SUM(1,0,N,Q[u].start,Q[u].start)+num_state[u]>0){
					v=next;
				}else{
					u=next;
				}
			}
		}

		if(u!=v){
			if(num_state[u]==1)return u+1;
			else if(num_state[v]==1)return v+1;
			else return -1;
			
		}else{
			if(num_state[u]==1)return u+1;
			else return -1;
		}
	}else{
		if(num_state[u]==1)return u+1;
		else return -1;
	}

	
}

// 0-base
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> N;
	fill(num_state,num_state+N,0);
	for(int i=0;i<N-1;i++){
		ll u,v;
		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);
	segment(1,0,N);
	
	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,k;
		cin >> q >> v;
		v--;
		if(q==1){
			num_state[v]^=1;
			if(num_state[v]==1){
				update(1,0,N,Q[v].start,Q[v].end,1);
			}else{
				update(1,0,N,Q[v].start,Q[v].end,-1);
			}
		}else{
			ll ans=query(v);
			cout << ans << "\n";
		}
		
		


	} 
		
}