BOJ 백준 30092 슥삭슥삭 나무자르기

 

문제 : https://www.acmicpc.net/problem/30092

[ 문제 요약 ]

• 노드 N 개와, 간선이 N-1 개인 트리 정보가 주어지며, 쿼리에 답합니다.
• 쿼리는 A, B, C, D가 주어지며, A에서 B로 가는 최단 경로의 간선을 삭제했을 때, C에서 D로 갈 수 있다면 YES 출력, 없다면 NO 출력입니다.

 

[ 테스트 케이스 설명 ]

8 4		// 노드 수(2<=100,000), 쿼리수(1<=300,000)
1 2		// 연결된 두 노드번호로 양방향 연결
1 3
3 4
3 5
3 6
4 7
4 8
6 7 2 3	// A,B,C,D가 주어지며 A->B로 가는 최단 경로에 모든 간선제거 후, C->D로 가는 경로가 있다면 YES, 없으면 NO출력
6 7 7 8
4 6 1 5
4 7 4 8
//답
YES
NO
YES
YES

 

[ 문제 해설 ]

 

이 문제는 기본적인 HLD와 Lazy Propagation 문제입니다.

 

https://www.acmicpc.net/problem/16453 이 문제와 비슷하지만, 쿼리수가 더 많습니다.

 

최댓값 세그먼트 트리를 만들고, 간선이 연결되어 있는 것은 값이 0, 연결되어 있지 않다면 1을 표현하면 노드 간 이동 시 쉽게 연결 유무를 확인할 수 있습니다.

 

처음 A-B 노드를 지날 때, 해당 구간에 전부 1을 더해주고, 나중에 C-D 구간 지나면서 구간의 MAX 값을 찾아오면, 1이면 연결되어 있지 않은 것, 0이면 연결되어 있는 것으로 판단합니다.

 

그리고 A-B 노드를 다시 지나면서, 1을 더했던 것을 0으로 만들어 주기 위해 -1을 다시 더해줍니다.

 

여기서 중요한 것은, 세그먼트 트리의 인덱스마다 저장되는 값은 간선의 유무를 저장하는 것입니다. 예를 들어 A, B 노드가 있을 때 두 노드의 세그먼트 트리에 대응하는 인덱스가 ㄴ1,2라 하면, 간선의 값을 2에 저장합니다. 그래야 나중에 쿼리 시 정확한 간선을 탐색할 수 있습니다.

 

단순히 각 노드의 가중치를 저장하는 것이면 1,2에 각각의 가중치를 저장할 테지만, 간선 정보기 때문에 두 노드 중 자식 노드에 가중치를 저장해야 일관적으로 값을 구할 수 있습니다.

 

HLD 알고리즘의 기본 설명은 아래 링크에 나와있습니다.

https://kyjdummy.tistory.com/21

BOJ 백준 13510 트리와 쿼리 1

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
class Main{
	
	static int N, Q;
	static int idx;				// 노드번호 -> 세그먼트 트리 인덱스 변환할 변수
	static int[] tree;			// 세그먼트 트리
	static int[] lazy;			// lazy propagation을 위한 배열
	static int[] treeIdx;			// 노드번호 -> 세그먼트 트리 인덱스 변환 정보를 담은 배열
	static int[] chainHead;			// 체인의 head값
	static int[] chainLevel;		// 체인의 level
	static int[] chainParent;		// 이전 체인으로 점프를 위한 이전 체인의 도착노드 값
	
	static ArrayList<Integer>[] adNode;
	
	public static void main(String[] args)throws Exception{
		BufferedReader	br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer	st = new StringTokenizer(br.readLine());
		StringBuilder	sb = new StringBuilder();
		N		= Integer.parseInt(st.nextToken());
		Q		= Integer.parseInt(st.nextToken());
		treeIdx		= new int[N + 1];
		chainHead	= new int[N + 1];
		chainLevel	= new int[N + 1];
		chainParent	= new int[N + 1];
		tree		= new int[N * 4];
		lazy		= new int[N * 4];
		adNode		= new ArrayList[N + 1];
		
		for(int i=0; i<=N; i++)
			adNode[i] = new ArrayList<>();
		
		for(int i=1; i<N; i++)
		{
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adNode[a].add(b);
			adNode[b].add(a);
		}
		
		// 이 함수에서 자식 노드의 크기를 확인하여 인접노드에 첫번째에 가장 무거운 노드를 오게 한다.
		setSize(1, 0, new int[N + 1]);
		// 1번 노드의 헤드는 자기자신
		chainHead[1] = 1;
		// HLD에 필요한 값 세팅
		setHLD(1, 0, 1);
		
		while(Q-->0)
		{
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			rangeUpdate(a, b, 1);	// a-b 노드 구간을 1로 업데이트하여 노드가 끊어짐을 표현
			
			sb.append(isConnect(c,d) ? "YES" : "NO").append('\n');
			
			rangeUpdate(a, b, -1);	// a-b 노드 구간을 다시 -1을 더해 노드 연결을 복구
		}
		System.out.print(sb);
	}
	static boolean isConnect(int n1, int n2) {
		// 체인 헤드가 같아질 때 까지 레벨을 올리면서 query결과가 true면 false를 반환해서 연결이 끊어짐을 알린다.
		while(chainHead[n1] != chainHead[n2])
		{
			if(chainLevel[n1] > chainLevel[n2])
			{
				int tmp = n1;
				n1 = n2;
				n2 = tmp;
			}
			// 쿼리 결과가 1이면 끊어진 것
			if(1 == query(1, 1, N, treeIdx[chainHead[n2]], treeIdx[n2]))
				return false;

			n2 = chainParent[n2];
		}
		if(treeIdx[n1] > treeIdx[n2])
		{
			int tmp = n1;
			n1 = n2;
			n2 = tmp;
		}
		// 쿼리 결과가 1이 아니여야 연결되어 있는 것
		return 1 != query(1, 1, N, treeIdx[n1] + 1, treeIdx[n2]);
	}
	static void rangeUpdate(int n1, int n2, int value) {
		// 체인 헤드가 같아질 때 까지 레벨을 올린다. 
		while(chainHead[n1] != chainHead[n2])
		{
			if(chainLevel[n1] > chainLevel[n2])
			{
				int tmp = n1;
				n1 = n2;
				n2 = tmp;
			}
			
			update(1, 1, N, treeIdx[chainHead[n2]], treeIdx[n2], value);
			
			n2 = chainParent[n2];
		}
		// 같은 체인이 되었으면 마지막으로 같은 체인 내에서 연산
		if(treeIdx[n1] > treeIdx[n2])
		{
			int tmp = n1;
			n1 = n2;
			n2 = tmp;
		}
		update(1, 1, N, treeIdx[n1] + 1, treeIdx[n2], value);
	}
	static int query(int treeNode, int s, int e, int left, int right) {
		propagate(treeNode, s, e);
		
		if(e < left || right < s)
			return 0;
		
		if(left<=s && e<= right)
			return tree[treeNode];
		
		int mid = (s + e) >> 1;
		
		return Math.max(query(treeNode << 1, s, mid, left, right),
						query(treeNode << 1 | 1, mid + 1, e, left, right));
	}
	static void update(int treeNode, int s, int e, int left, int right, int value) {
		propagate(treeNode, s, e);
		
		if(e < left || right < s)
			return;
		
		if(left<=s && e<= right)
		{
			lazy[treeNode] = value;
			propagate(treeNode, s, e);
			return;
		}
		
		int mid = (s + e) >> 1;
		
		update(treeNode << 1, s, mid, left, right, value);
		update(treeNode << 1 | 1, mid + 1, e, left, right, value);
		
		tree[treeNode] = Math.max(tree[treeNode << 1] , tree[treeNode << 1 | 1]);
	}
	static void propagate(int treeNode, int s, int e) {
		if(lazy[treeNode] != 0)
		{
			tree[treeNode] += lazy[treeNode];
			if(s != e)
			{
				lazy[treeNode << 1] += lazy[treeNode];
				lazy[treeNode << 1 | 1] += lazy[treeNode];
			}
			lazy[treeNode] = 0;
		}
	}
	static void setHLD(int nowNode, int parentNode, int level) {
		treeIdx[nowNode] = ++idx;
		chainLevel[nowNode] = level;
		
		for(int i=0; i<adNode[nowNode].size(); i++)
		{
			int next = adNode[nowNode].get(i);
			
			if(next == parentNode)
				continue;
			
			if(i == 0)	// heavy 노드는 체인 유지
			{
				chainHead[next] = chainHead[nowNode];
				chainParent[next] = chainParent[nowNode];
				setHLD(next, nowNode, level);
			}
			else		// light는 새로운 채인 생성
			{
				chainHead[next] = next;			// 새체인의 헤드는 자기자신
				chainParent[next] = nowNode;	// 이전 체인으로 점프를 위한 노드 세팅
				setHLD(next, nowNode, level + 1);// 새 체인은 level이 1증가한다.
			}
		}
	}
	static void setSize(int nowNode, int parentNode, int[] size) {
		int heavySize = 0;
		int heavyIdx = 0;
		size[nowNode] = 1;
		for(int i=0; i<adNode[nowNode].size(); i++)
		{
			int next = adNode[nowNode].get(i);
			
			if(next == parentNode)
				continue;
			
			setSize(next, nowNode, size);
			
			size[nowNode] += size[next];
			
			if(heavySize < size[next])
			{
				heavySize = size[next];
				heavyIdx = i;
			}
		}
		if(adNode[nowNode].size() > 0)
			Collections.swap(adNode[nowNode], 0, heavyIdx);
	}
}