Heavy Light Decomposition

1. 각 노드에서 light edge를 타고 갈 때마다 서브트리의 크기는 1/2 이하로 감소한다.

heavy edge가 가장 서브트리의 크기가 큰 간선이므로, 만약 light edge를 타고 가도 서브트리의 크기가 1/2 초과로 유지된다면, $sz[heavy]>=sz[light]>N/2$, $sz[heavy]+sz[light]>N$으로 모순이다.

 

2. 각 노드에서 루트 방향으로 부모를 타고 올라갈 때 만나는 light edge의 개수는 $O(logN)$개이다.

Property 1에 의해 light edge를 타고 내려가면 서브트리의 크기가 1/2 이하로 감소하니, light edge를 타고 올라가면 서브트리의 크기가 2배 이상으로 증가한다. 전체 트리의 노드의 수가 N개 이니, light edge의 수는 최대 $O(logN)$개임을 알 수 있다.

이 성질로 인해 흔히 사용하는 HLD에서 트리상의 하나의 경로를 최대 $O(logN)$개의 체인만을 지나도록 쪼갤 수 있다.

 

3. 각 노드에서 heavy edge를 제외한 light edge들의 서브트리의 크기를 모두 합해도 $O(NlogN)$이다.

각 노드별 light edge의 서브트리의 합을 세는 대신, 각 노드별 그 노드를 light edge의 서브트리로 갖는 부모 노드의 수를 세면 Property 2에 의해 최대 $O(logN)$개 이니, 전체 노드에 대해서는 $O(NlogN)$개 이다.

 

4. 루트에서 정점까지의 경로의 모든 정점에 서로 다른 색으로 색칠하는 업데이트가 있을 때, 루트에서 정점까지의 경로의 모든 정점 상의 서로 다른 색의 수의 합은 amortized $O(NlogN)$이다. (JOISC18 Highway)

같은 색은 하나의 경로로 묶여 있으니, 쿼리당 묶음의 수의 합이 $O(NlogN)$임을 보여야 한다.

업데이트 직후, 각 간선별로 부모와 자식의 색이 다르다면 그 간선을 "separator"이라 부르자.

separator의 수가 곧 묶음의 수이니, 각 업데이트별 지나는 separator의 수의 합이 $O(NlogN)$임을 보이자.

업데이트될 노드에서 루트까지의 경로가 지나는 light edge의 수는 $O(logN)$개 이니, light edge들이 모두 separator이라도 무관하다.

만약 heavy edge가 separator이라면, 그 말은 현재 부모 노드의 간선들 중 separator이 아닌 간선은 하나의 light edge에 해당한다는 것을 알 수 있다. 이는 현재의 업데이트 전에 추가된 노드들 중 부모 노드의 서브트리에 포함되는 가장 마지막으로 등장한 정점은 heavy edge를 제외한 부분의 노드라는 것이다. 또한, 지금 업데이트에서 heavy edge가 separator이라는 것은 지금 업데이트될 정점은 heavy edge의 서브트리이다. 정리하자면, heavy edge가 separator이기 위해서는 무조건 그 전에 한번은 부모 노드의 서브트리 중 heavy edge를 제외한 부분의 업데이트가 가장 마지막으로 등장했어야 함을 의미한다. 이 heavy edge가 separator이 되는 순간을 해당하는 마지막 light edge의 업데이트와 1대1 대응시킬 수 있기 때문에, heavy edge가 separator이 되는 횟수의 최댓값은 light edge 부분의 서브트리의 노드들의 수의 합과 같다.

HLD에서 각 노드들에 대해 heavy edge를 제외한 부분의 서브트리의 노드들의 개수의 합은 최대 $O(NlogN)$이니, 전체 업데이트별 지나는 separator의 수도 $O(NlogN)$과 같다.