국제 옥토끼 기구

https://www.acmicpc.net/problem/17348

풀이 1 ($O(N \log N + Q \log^2 N)$)

Centroid decomposition을 이용한다.

각 센트로이드 $C$에 대해서 $C$가 담당하는 부분 트리의 각 정점 $V$에 대해 $distance(C, V)$를 모아서 정점 번호 기준으로 세그먼트 트리를 만들 수 있다.

쿼리로 받은 정점 $V$에서 부모 센트로이드로 올라가면서 아직 처리되지 않은 정점들 중에 $[L, R]$ 구간에 속하는 정점의 값을 계속해서 더해주어 답을 구할 수 있다. 이때 현재 처리된 정점들은 현재 센트로이드를 기준으로 했을 때 $V$가 속하는 서브트리의 정점들이고, 이 서브트리들의 정점을 제외하고 계산할 수 있는 세그먼트 트리를 만들면 된다. 쿼리의 답을 구하는 과정을 아래의 pseudo-code와 같이 구현할 수 있다.

result query(int L, int R, int V) {
    result ret;
    for (int centroid = V; valid(centroid); centroid = parent_centroid(child_centroid = centroid)) {
        ret.apply(segment_tree(centroid).get(left = L, right = R,
        except_subtree_index = subtree_index(centroid = centroid, vertex = V)) + distance(V, centroid));
    }
    return ret;
}

트리를 전처리하는 시간복잡도는 $O(N \log N)$이고, 각 쿼리의 시간복잡도는 $O(\log^2 N)$이다.

풀이 2 ($O((N + Q) \log N)$)

$[1, N]$ 구간을 세그먼트 트리의 노드처럼 $[S_i, E_i]$ 형태의 구간 $O(N)$개로 나눌 수 있다. 이때 $\sum\limits_i (E_i-S_i+1)=O(N \log N)$이다. 이렇게 나누면 각 쿼리 $(L, R, V)$를 $\sum\limits_j (S_{i_j}, E_{i_j}, V)$와 같이 $O(\log N)$개의 쿼리로 분할할 수 있다. 이제 각 구간 $[S_i, E_i]$에 대해 정점 $[S_i, E_i]$와 $V$의 거리를 구하는 쿼리를 수행하면 된다. 이러한 쿼리의 개수는 $O(Q \log N)$개가 된다.

어떤 구간 $[S_i, E_i]$에 대해 쿼리 $V_1, V_2, \cdots, V_{Q_i}$가 존재할 것이다. 정점 $[S_i, E_i]$와 $V_j$를 모두 모은 후 트리 압축을 하면, $O(E_i-S_i+1+Q_i)$의 시간복잡도에 DFS로 모든 답을 구할 수 있다. 트리 압축을 하는 과정에서 DFS order로 정렬을 해야 하는데, 모든 구간 $[S_i, E_i]$에 대해서 정렬해야 하는 수들을 모은 후 카운팅 정렬을 하면 $O(N+\sum\limits_i(E_i-S_i+1+Q_i))=O((N+Q)\log N)$의 시간복잡도로 트리 압축을 모두 실행할 수 있다. 마지막으로 DFS를 통해 답을 구하는 과정은 $O(\sum\limits_i(E_i-S_i+1+Q_i))=O((N+Q)\log N)$이 되며, 총 $O((N+Q)\log N)$의 시간복잡도로 문제를 해결할 수 있다.