백준13510 C++ 풀이 - HLD

---

HLD (Heavy-Light Decomposition) 의 개념을 처음 접하게 해준 문제이다.

---

1. 접근

트리인 것이 보장되어 있고, u->v 로 갈 수 있는 최단 경로에서 간선 중 가장 높은 값을 찾아야 한다.

 

처음 접근은 최단 경로를 구하기 위해 LCA 를 구현했다.

u -> lca, lca -> v 를 연결하는 간선을 차례대로 조회하며 최대값을 갱신하면 답을 낼 수 있었다.

 

하지만 위 방식은 쿼리 하나 당 O(N)의 시간을 요구했다.

쿼리 M개(<=100,000)를 2초 안에 해결하려면 M * Log N 수준의 최적화가 필요했다.

 

하루 반을 꼬박 생각해봤지만, query(u, lca) 를 인덱스 트리를 이용하여 구할 순 없었다.

그 이유는 u -> lca 의 경로가 순차적으로 존재하고 있지 않았기 때문이다.

 

인덱스트리는 연속된 구간에서 합/최대 등을 빠르게 뽑아낼 수 있는 방식이었는데,

지금의 경우는 트리의 구조이며, 인접 노드의 번호가 연속되지 않기 때문에 사용할 수 없었다.

(예를 들어, 1->2->3->4 처럼 순차적이지 않고 1->4 ->2 ->3 처럼 자기 멋대로 트리가 구성될 수도 있다..!)

 

그래서 결국 검색을 해본 결과 아주아주 도움이 되는 블로그의 글을 발견할 수 있었다.

Heavy Light Decomposition | JusticeHui가 PS하는 블로그

Heavy Light Decomposition

이해하기 정말 쉽게 그림을 그려주셨다. 그림을 반드시 참고하자.

---

2. HLD 

트리의 한 노드에서 자식 노드로 갈 때

가장 무거운(Heavy)노드 하나와

상대적으로 가벼운(Light) 노드들을 구별하여

개별 그룹으로 구분한다.

 

이 때, 노드들을 하나의 그룹으로 묶은 것을 체인(Chain)이라고 부른다.

 

본래 무겁다의 기준은 현재 노드의 SubTree의 크기의 반보다 큰 SubTree를 가진 자식 노드를 뜻한다.

(subTreeSize[cur] / 2 <= subTreeSize[child])

 

그렇기 때문에 무거운 노드를 하나 거쳐서 내려갈 때마다 남은 Tree size가 1/2씩 작아지게 된다.

 

하지만, 구현의 편리함을 위해 실제 구현시에는

무거운 노드를

자식 노드 중 SubTree 의 크기가 가장 큰 것으로 생각한다.

 

현재 노드에서 무거운 노드를 통해 내려가면서 체인을 구성한다.

한편, 가벼운 노드는 그 노드를 루트 노드로 하여 새로운 체인을 구성하게 되며, 

그 다음부터 무거운 노드를 따라가며 또 새로운 체인을 구성하게 되므로,

분할정복의 형상을 띈다.

 

체인을 구성할 때 가장 중요한 점은 다음과 같다. (gatherIndex() 함수 참고)

1. 같은 체인에 속한 노드들은 인덱스 트리의 리프노드 상에서 서로 인접해야 한다. 

2. 가벼운 노드는 새로운 체인의 루트 노드가 되며 무거운 노드는 루트 노드와 같은 체인에 속한다.

 

같은 체인에 속한 노드들을 인접하게 하는 방법은 re-indexing 으로 생각하면 될 것 같다.

node -> in[node] (방문한 순서) -> index tree 리프노드에 추가

즉, 1->3->2 로 방문했다면 in[1] = 1, in[2] = 3, in[3] = 2 로 저장될 것이므로

index tree leaf node의 1번에는 1번node에 대한 정보,

2번에는 3번node에 대한 정보, 

3번에는 2번 node에 대한 정보가 들어가면 된다.

 

이런 식으로 연관된 노드들을 선형으로 표현해주고, 해당 범위에 대한 쿼리를 indexTree 방식으로

날려주면 O(MlogN)의 시간 복잡도를 가진다.

---

3. 그래서 어떻게 답을 구하냐

u - > v 로 가는 루트 중 최대값을 구하려면 LCA를 구하는 대신 Chain 을 통해 봐야한다.

u 와 v 가 같은 Chain에 속하지 않았다면 Chain 을 위로 점점 올리면서 

같은 Chain 에 속할 때까지 올려야 한다. 

 

실제로 구현할 때는 간선 정보가 바뀔 때 어떻게 트리를 바꿔 줄 것이냐이다.

 

HLD 는 노드를 중심으로 하는데, 위 문제는 간선에 값이 존재하기 때문에

부모/자식 노드 중 하나를 선택하여 정보를 저장해야 인덱스트리를 쓸 수 있다.

 

부모는 2개 이상의 자식을 가질 수 있기 때문에,

부모에 값을 저장하면 어떤 자식에서 온 값인지 모른다.

 

반면, 자식은 무조건 하나의 부모만을 가지기 때문에, 

자식 -> 부모로 가는 간선 값을 자식 노드에 저장해야 한다.

 

간선의 값을 자식 노드에 저장해놓았기 때문에

인덱스 트리에 노드 번호를 날릴 때도 주의해야 한다.

Chain의 루트노드까지 포함하여 Max 값을 계산할 경우

Chain의 루트노드에서 다른 체인으로 넘어가는 간선의 값까지 같이 계산하게 되므로

의도치 않은 값을 얻을 수 있다.

 

이를 방지하기 위해 query() 함수에서는 u,v가 같은 Chain에 속할 때

더 높은 노드의 인덱스에 +1을 해준다.

예를 들어 원래 1~4 까지 물어봐야 했다면 2~4까지만 물어봐야

부모 노드 하나를 제거하고 최대값을 구할 수 있다는 뜻이다.

 

 

 

공간 복잡도를 줄일 수 있는 방법에 대해 찾아봐야 할 것 같다 ^^;

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int N, u, v, w, M,num,base=1;
int parent[100001], //자신의 부모
tree[400001],		//index tree 구성할 것
in[100001],			//해당 노드가 불린 순서
dep[100001],		//해당 노드의 깊이depth
sz[100001],			//해당 노드의 subtree의 size(자기자신1포함)
chain[100001];		//해당 노드가 속한 체인의 최상위 노드
pair<int,pair<int,int>> edge[100001];//간선 입력받기
vector<int> adj[100001];//인접 간선 표시
vector<int> adjTree[100001];//단방향 트리 구성


//단방향 트리 생성, 1번 노드부터
void makeAdjTree(int prev = -1, int cur = 1) {
	for (auto& i : adj[cur]) {
		if (prev == i) continue;
		adjTree[cur].push_back(i);
		makeAdjTree(cur, i);
	}
}

//sz, dep, parent 생성 + 단방향 트리에서 subtree size 가 가장 큰 것을 가장 앞으로(0번으로)
void build( int cur= 1) {
	sz[cur] = 1;
	for (auto& i : adjTree[cur]) {
		dep[i] = dep[cur] + 1;
		parent[i] = cur;
		build(i);
		sz[cur] += sz[i];
		if (sz[adjTree[cur][0]] < sz[i]) swap(adjTree[cur][0], i);
	}
}

//in, chain 생성
void gatherIndex(int cur = 1) {
	in[cur] = num++;
	for (auto& i : adjTree[cur]) {
		if (i == adjTree[cur][0]) {
			chain[i] = chain[cur];
		}
		else {
			chain[i] = i;
		}
		gatherIndex(i);
	}
}

//인덱스 트리를 업데이트, i번째 간선 정보를 찾아서 트리에 넣어서 업뎃해줌
void update(int i, int c) {
	int u = edge[i].second.first;
	int v = edge[i].second.second;
	edge[i].first = c;
	if (parent[v] ^ u) swap(u, v);
	int idx = base + in[v];
	tree[idx] = edge[i].first;
	while (idx >>= 1) {
		tree[idx] = max(tree[idx << 1], tree[idx << 1 | 1]);
	}

}

//index Tree 에서 l~r 중 max 값 찾기 
int maxQuery(int l, int r) {
	int ret = 0;
	//항상 v 가 더 깊음
	l |= base;
	r |= base;
	while (l <= r) {
		if (l & 1) ret = max(ret, tree[l++]);
		if (~r & 1) ret = max(ret, tree[r--]);
		l >>= 1;
		r>>= 1;
	}
	return ret;
}

//u <-> v 단순 간선 중 최대간선 값
int query(int u, int v) {
	int ret = 0;
	while (chain[u] ^ chain[v]) {
	//항상 u가 더 위에있음
		if (dep[chain[u]] > dep[chain[v]]) swap(u, v);
		ret = max(ret, maxQuery(in[chain[v]], in[v]));
		v = parent[chain[v]];
	}
	if (in[u] > in[v]) swap(u, v);
	
	ret = max(ret, maxQuery(in[u] + 1, in[v]));
	return ret;
}

int main() {
	scanf("%d", &N);
	//인덱스 트리 리프노드 시작점
	while (base < N) base <<=1;
	//입력
	for (int i = 1; i < N; ++i) {
		scanf("%d %d %d", &u, &v, &w);
		edge[i].first = w;
		edge[i].second.first = u;
		edge[i].second.second = v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	makeAdjTree();
	build();
	gatherIndex();
	//인덱스트리생성
	for (int i = 1; i < N; ++i) update(i, edge[i].first);

	scanf("%d", &M);
	for (int i = 0; i < M; ++i) {
		scanf("%d %d %d", &u, &v, &w);
		switch (u) {
		case 1:
			update(v, w);
			break;
		case 2:
			printf("%d\n",query(v, w));
			break;
		}
	}

}