트리에서의 쿼리

이 글에서는 트리에 대한 문제를 이미 알려진 자료 구조로 풀 수 있는 구간 문제로 환원하는 다양한 방법을 살펴봅니다.

읽기 전에 깊이 우선 탐색으로 얻는 배열 $tin$과 $tout$의 성질을 떠올려 보는 것을 권장합니다.

#서브트리에 대한 쿼리

dfs의 첫 번째 중요한 성질은 임의의 서브트리에 속한 정점들의 $tin$ 값이 어떤 연속된 구간을 이룬다는 것입니다.

이 성질을 이용하면 서브트리에 대한 다양한 쿼리를 부분 구간에 대한 쿼리로 바꾸어 처리할 수 있으며, 이러한 쿼리는 이미 표준적인 방법, 예를 들어 세그먼트 트리로 해결할 수 있습니다.

#서브트리에서의 합

문제. 루트가 있는 트리가 주어집니다. 각 정점 옆에는 수가 하나씩 적혀 있습니다. 두 종류의 쿼리가 들어옵니다: 값 중 하나를 변경하는 쿼리와 정점 $v_i$의 서브트리에 있는 값들의 합을 구하는 쿼리입니다.

각 정점에 적힌 모든 수를 하나의 배열에 옮겨 적되, 각 수를 해당 정점의 $tin$ 값에 해당하는 위치에 둡시다. 이 배열의 관점에서 «정점 $v$의 서브트리에서의 합»이란 무엇입니까? 이는 단순히 부분 구간 $[tin_v, tout_v)$에서의 합입니다.

배열 위에 세그먼트 트리 또는 동적 합을 처리하는 다른 임의의 자료구조를 구축합시다. 첫 번째 유형의 쿼리에 대해서는 자료구조에 칸 변경 쿼리 $a_{tin_v} = x$를 보내고, 두 번째 유형의 쿼리에 대해서는 부분 구간 $[tin_v, tout_v)$에 대한 합 쿼리를 수행합니다.

#레벨별 쿼리

$tin$과 $tout$ 외에도, 순회하는 동안 정점의 깊이를 계산해 두면 유용할 때가 있습니다. 앞으로 이를 $depth_v$로 표기하겠습니다.

#Level Ancestor

문제. 루트가 있는 트리가 주어집니다. 정점 $v_i$의 $d_i$번째 조상, 즉 $v_i$로부터 거리 $d_i$만큼 떨어진 조상 정점을 찾는 쿼리에 답해야 합니다.

$h$개의 벡터를 만듭시다. 여기서 $h$는 트리의 높이입니다. 각 정점에 대해 dfs로 순회하는 동안 그 정점의 $tin$을 해당 정점의 깊이에 대응하는 벡터에 추가합시다. 그러면 정렬된 벡터 $h$개를 얻습니다.

이제 하나의 벡터 안에서 정점들의 서브트리 구간 $[tin_v, tout_v)$ 역시 서로 겹치지 않으며, 따라서 정렬되어 있다는 점에 주목합시다. 그러면 쿼리에 답하기 위해 쿼리 정점의 $tin$을 가져와 필요한 레벨의 벡터를 살펴보고, $O(\log n)$ 시간에 필요한 구간에 대해 이진 탐색을 수행하기만 하면 됩니다.

또한 쿼리당 $O(1)$의 시간이 들지만 전처리에 $O(n \log n)$의 메모리가 필요한 다른 방법도 있습니다. 바로 사다리 분할입니다.

#주어진 깊이의 서브트리

문제. 루트가 있는 트리가 주어집니다. 각 정점 옆에는 수가 하나씩 적혀 있습니다. 두 종류의 쿼리가 들어옵니다: 값 중 하나를 변경하는 쿼리와, 정점 $v_i$의 서브트리에서 그 정점으로부터 거리가 $k_i$ 이하인 정점들의 값의 합을 구하는 쿼리입니다.

깊이와 트리 구조를 동시에 사용할 때는 보통 문제를 기하학적으로 바라보는 것이 도움이 됩니다. 각 정점에 점 $(tin_u, depth_u)$를 대응시킵시다. 그러면 구하려는 정점 집합은 어떤 모습입니까? 이 집합은 첫 번째 좌표가 $tin_v$와 $tout_v$ 사이에 있고 두 번째 좌표가 $depth_v$보다 큰 점들에 대응합니다.

따라서 이러한 서브트리에 대한 쿼리는 직사각형에 대한 쿼리로 환원할 수 있으며, 이는 2차원 자료구조로 “정면으로” 풀거나 스위프 라인과 같은 기법을 적용하여 해결할 수 있습니다.

#경로 쿼리

경로에 대한 쿼리가 오프라인으로 주어진다면, 거의 항상 어떤 전처리를 통해 해결할 수 있습니다.

#경로 위의 합

문제. 트리가 주어집니다. 각 간선에는 어떤 수가 하나씩 적혀 있습니다. 경로 위의 합을 구하는 쿼리에 답해야 합니다.

깊이 우선 탐색을 하는 동안 배열 $s$를 미리 계산해 둡시다. 여기서 $s_v$는 루트에서 정점 $v$까지의 경로 위에 있는 수들의 합입니다.

트리의 모든 경로는 하나 또는 두 개의 수직 경로로 나뉩니다. 최소 공통 조상 $c = lca(a, b)$을 찾아 합을 $(s_a + s_b - 2 \cdot s_c)$로 나눕니다.

#경로 위의 Xor

문제. 트리가 주어집니다. 각 간선에는 어떤 수가 하나씩 적혀 있습니다. 경로 위의 xor-합을 구하는 쿼리에 답해야 합니다.

xor-합의 경우에는 이러한 경로를 찾을 필요조차 없다는 점에 주목하십시오. 2를 법으로 하면 항 $2 \cdot s_c$가 스스로를 «상쇄»하기 때문입니다. 단순히 s[a] ^ s[b]를 출력하기만 하면 됩니다.

#경로 위의 서로 다른 수의 개수

문제. 트리가 주어집니다. 각 간선에는 어떤 수가 하나씩 적혀 있습니다. $v$에서 $u$로 가는 경로 위에 있는 서로 다른 값의 개수를 구하는 $q$개의 쿼리에 답해야 합니다.

더 복잡한 쿼리를 오프라인으로 처리하려면 거의 항상 Mo 알고리즘을 트리로 일반화한 방법을 사용해야 하며, 그 방법은 대략 다음과 같습니다.

• 트리의 오일러 투어를 적어 봅시다. 간선을 지날 때마다 그 간선의 번호(아래쪽/위쪽 정점의 번호)를 적습니다. 각 간선은 아래쪽 정점에 들어갈 때와 나올 때, 이렇게 두 번 적힌다는 점에 주목하십시오.
• 쿼리를 받으면 「더 이른」 정점 $v$($tin_v$가 더 작은 정점)를 정하고, 오일러 투어에서 $tin_v$부터 $tin_u$까지의 부분 구간을 살펴봅시다.
• 이 구간에 있는 간선들의 어떤 부분 수열은 $v$와 $u$ 사이의 최단 경로입니다. 정확히 말하면, 이 구간에서 정확히 한 번 나타난 간선들이 바로 그것이며, 두 번 나타난 간선들은 모두 경로에서 벗어난 어떤 부분 트리로 이어집니다.

이제 순회에서 간선 번호 옆에 그에 대응하는 수도 함께 적어 둡시다. 그러면 경로 위의 서로 다른 값의 개수를 구하는 질의는 부분 구간에서 정확히 한 번 등장하는 간선들이 가진 서로 다른 값의 개수를 구하는 것과 동치입니다. 이 문제는 이제 일반적인 Mo 알고리즘으로 해결할 수 있습니다.