트리에서의 Mo's Algorithm을 위한 쿼리 변형하기

0. 요약

트리에서 서브트리에 대한 쿼리, 경로에 대한 쿼리가 주어질 때,

이를 배열의 구간에서 특정 횟수만큼 등장하는 원소에 대한 쿼리로 변형할 수 있다.

=> Mo's Algorithm 적용 가능한 꼴!

---

1. 트리 펼치기

트리를 펼치는 것은 보통 트리를 노드 번호의 수열로 나타내는 것을 뜻하며, 그 목적에 따라 다양한 방법이 존재한다.

이 글에서는 트리에서 Euler tour를 돌면서(dfs를 수행하면서) 각 정점을 처음 방문했을 때 / 마지막으로 방문했을 때 배열에 기록하는 방법을 이용하고자 한다.

 

예를 들어 위와 같은 트리에서 1번을 root로 하여 dfs를 수행하되 번호가 작은 정점을 먼저 방문한다고 하자.

단순히 정점을 방문하는 순서는 1, 2, 3, 4, 5, 6, 7, 8, 9지만, 각 정점을 처음 방문했을 때(dfs함수 진입시)와 마지막으로 방문했을 때(dfs함수 return시)마다 배열에 기록한다면 다음과 같은 결과를 얻게 된다.

 

또한 처음 방문하는 시각/마지막으로 방문하는 시각을 start, end라고 하면 다음과 같이 나타난다.

(시각: 각 occerrence가 arr배열에서 존재하는 위치)

 

v	start(v)	end(v)
1	1	18
2	2	11
3	3	8
4	4	5
5	6	7
6	9	10
7	12	17
8	13	14
9	15	16

 

2. 쿼리 변형하기

이러한 정보를 토대로 트리에서 서브트리에 대한 쿼리, 경로에 대한 쿼리가 주어질 때, arr배열의 구간에서 특정 횟수만큼 등장하는 원소에 대한 쿼리로 변형하여 문제를 해결할 수 있다.

 

1) 정점 v의 서브트리에 대한 쿼리

<=> arr[start(v) ~ end(v)]에서 정확히 2번 등장하는 정점에 대한 쿼리

 

정확히 2번 등장하는 정점: 2, 3, 4, 5, 6

2) 정점 p에서 정점 q까지의 경로 상의 정점에 대한 쿼리

일반성을 잃지 않고 start(p) <= start(q)라고 하자. 또 L = lca(p, q)라고 하자.

• end(p) >= end(q)인 경우
  • p가 q의 조상인 경우, 즉 L = p인 경우를 의미한다.
  • arr[start(p) ~ start(q)]에서 정확히 1번 등장하는 정점들이 p~q 경로 상의 정점이다.

정확히 1번 등장하는 정점: 2, 3, 5

• end(p) < end(q)인 경우
  • L != p인 경우를 의미한다.
  • arr[end(p) ~ start(q)]에서 정확히 1번 등장하는 정점들이 p~q 경로 상의 정점이다.
  • 단, L은 예외적으로 0번 등장하지만 경로 상의 정점이다.

정확히 1번 등장하는 정점: 3, 2, 7, 8