BOJ 백준 13038 Tree
문제 : 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);
}
}