kyjdummy 2025. 4. 29. 22:03

 

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

[ 문제 요약 ]

  • 트리가 주어지며, 정점 사이 거리는 1입니다.
  • 2개 유형의 쿼리가 주어지며, 쿼리 유형이 1이면 주어지는 두 a, b 노드 사이의 거리를 출력, 쿼리 유형이 2이면 주어지는 v 노드의 부모와 연결을 끊고, v 노드의 자식 노드들은 그 부모와 연결시킵니다.

 

[ 테스트 케이스 설명 ]

8		// 정점 개수(1<=100,000)
1 5 2 1 2 5 5	// 1번은 루트, 2번노드부터 그 부모 노드가 주어짐
7		// 질문개수 (1<=100,000)
2 4
1 7 6		// 쿼리 유형이 1이면 a,b가 주어지고, 두 정점 사이 거리 출력
2 5		// 쿼리 유형이 2이면 그 뒤 정수 v가 주어지며, v정점을 제거한다.
1 3 8
1 8 6
2 2
1 8 6
//답
4
2
3
2

 

 

[ 알고리즘 분류 ]

  • 자료구조
  • 트리
  • 세그먼트 트리
  • 최소 공통 조상
  • 오일러 경로 테크닉
  • heavy-light 분할

 

[ 문제 해설 ]

 

이 문제도 전형적인 HLD + 세그먼트 트리 문제입니다.

 

주어지는 트리 정보는 바로 세그먼트 트리에 적용할 수 없기 때문에, HLD를 사용해 트리를 여러 개의 체인으로 분할하고, 각 노드당 세그먼트 트리에 대응하는 인덱스를 저장하여 문제를 풉니다.

 

세그먼트 트리는 구간 합 세그먼트 트리를 작성합니다. 그래야 경로를 따라 올라가며 구간 합으로 거리를 쉽게 구할 수 있습니다.

 

그리고 주어지는 쿼리 유형에 따라 노드의 간선을 제거하던가, 두 노드의 거리를 출력합니다.

 

여기서 중요한 것은, 두 노드 사이에 간선의 정보를 어디에 저장해야 하느냐입니다.

 

A-B 노드가 있을 때, A를 부모 노드, B를 자식 노드라 하면 간선 정보는 B 노드 즉, 자식 노드에 저장합니다. 그래야 문제 조건에 맞게 간단한 게 코드를 짤 수 있습니다.

 

간선 정보를 자식 노드에 저장했기 때문에, 최종적으로 마지막 구간 합 쿼리를 실행할 때는

 

부모 노드 자신은 쿼리 구간에서 빠져야 합니다. 코드는 아래와 같습니다.

 

ans += query(1, 1, N, treeIdx[a] + 1, treeIdx[b]);

 

위 코드에서 treeIdx[a] + 1을 하는데, 이렇게 하지 않고, treeIdx[a]를 해버리면, a의 부모 노드로 가는 간선의 값까지 가져오므로 제대로 된 값을 갖고 올 수 없습니다.

 

HLD에 대한 설명은 아래 문제에서 디테일하게 설명했습니다.

https://kyjdummy.tistory.com/21

 

BOJ 백준 13510 트리와 쿼리 1

문제 : https://www.acmicpc.net/problem/13510[ 문제 요약 ]N 개의 노드와 N - 1개의 간선이 주어지며 2가지 명령어가 임의로 주어집니다.1 i c : i 번 간선의 비용을 c로 변경2 u v : u에서 v로 가는 단순 경로에

kyjdummy.tistory.com

 

나머지 설명은 코드를 통해 확인 가능합니다.

 

[ 정답 코드 ]

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 [] 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));
		StringBuilder	sb = new StringBuilder();
		
		N		= Integer.parseInt(br.readLine());
		tree		= new int[N * 4];
		treeIdx		= new int[N + 1];
		chainHead	= new int[N + 1];
		chainLevel	= new int[N + 1];
		chainParent	= new int[N + 1];
		adNode		= new ArrayList[N + 1];
		
		for(int i=0; i<=N; i++)
			adNode[i] = new ArrayList<>();
		
		StringTokenizer	st = new StringTokenizer(br.readLine());
		for(int child=2; child<=N; child++)
		{
			int parent = Integer.parseInt(st.nextToken());
			// 양방향 연결
			adNode[parent].add(child);
			adNode[child].add(parent);
		}
		
		// HLD 세팅을 위해 자식 노드가 큰것을 인접리스트에서 가장 첫번째로 옮긴다.
		setSize(1, 0, new int[N + 1]);
		
		chainHead[1] = 1;// 1번 노드 헤드는 자기자신
		
		// 해당 함수에서 논리적인 체인으로 나누고, chain정보를 입력한다.
		setHLD(1, 0, 1);
		
		// 간선의 정보를 세그먼트 트리에 저장해야 하므로, 부모-자식 노드 관계에서 자식노드에 간선 정보를 저장한다.
		for(int child=2; child<=N; child++)
			update(1, 1, N, treeIdx[child], 1); // 1번 노드를 제외한 자식 노드들의 위치에 1을 더해서 간선 연결을 표현한다.

		Q = Integer.parseInt(br.readLine());// 질문개수 (1<=100,000)
		
		while(Q-->0)
		{
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());

			if(op == 1)// 쿼리 유형이 1이면 a,b가 주어지고, 두 정점 사이 거리 출력
			{
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int ans = 0;
				// 같은 체인이 될 때까지 레벨을 낮춘다.
				while(chainHead[a] != chainHead[b])
				{
					if(chainLevel[a] > chainLevel[b])
					{
						int tmp = a;
						a = b;
						b = tmp;
					}
					// b노드가 속한 체인의 전체 간선 정보를 쿼리해와서 ans에 더함 
					ans += query(1, 1, N, treeIdx[chainHead[b]], treeIdx[b]);
					
					b = chainParent[b];	// 다음체인으로 바로 점프
				}
				// 같은 체인이 되었다면, 같은 체인 내에서 마지막 연산을 진행
				if(treeIdx[a] > treeIdx[b])
				{
					int tmp = a;
					a = b;
					b = tmp;
				}
				
				ans += query(1, 1, N, treeIdx[a] + 1, treeIdx[b]);// 자식 노드에 간선정보를 저장하였으므로 시작은 + 1을 한다.
				
				sb.append(ans).append('\n');
				
				continue;
			}
			
			// 쿼리 유형이 2이면 그 뒤 정수 v가 주어지며, v정점을 제거한다.
			int v = Integer.parseInt(st.nextToken());
			// 해당 노드에 0을 대입해 노드 삭제를 표현
			update(1, 1, N, treeIdx[v], 0);
		}
		System.out.print(sb);
	}
	static int query(int treeNode, int s, int e, int left, int right) {
		if(e < left || right < s)
			return 0;
		
		if(left<=s && e<=right)
			return tree[treeNode];
		
		int mid = (s + e) >> 1;
		
		return 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 targetIdx, int value) {
		if(e < targetIdx || targetIdx < s)
			return;
		
		if(s == e)
		{
			tree[treeNode] = value;
			return;
		}
		
		int mid = (s + e) >> 1;
		
		update(treeNode << 1, s, mid, targetIdx, value);
		update(treeNode << 1 | 1, mid + 1, e, targetIdx, value);
		
		tree[treeNode] = tree[treeNode << 1] + tree[treeNode << 1 | 1];
	}
	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 증가
			}
		}
	}
	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);
	}
}