트리에서의 모스 알고리즘 활용 ( Mo's algorithm on tree )

Table of Contents

개요

트리 펼치기

Mo's algorithm 의 적용

문제

1. 개요

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

 위 문제와 같이 트리에서의 쿼리를 처리할 때, 쿼리의 처리 순서를 마음대로 조작할 수 있다면, DFS로 트리 펼치기 + Mo's algorithm 의 조합으로 시간 복잡도 O( (N+Q) * sqrt N * f(x) ) 을 맞춰 줄 수 있는 경우들이 있습니다.

( * f(x) = 모스 알고리즘에서 노드의 추가 / 삭제 시 필요한 시간복잡도 )

2. 트리 펼치기

 트리에서 DFS를 돌면서, 각각의 DFS 함수가 '시작 했을 때', 그리고 '끝날 때' 해당하는 노드를 배열에 추가해서 트리를 펼치는 스킬입니다. 아래 예시를 통해 알아보겠습니다.

위와 같은 트리를 배열로 펼친다면, arr[] = {1, 2, 5, 5, 4, 4, 2, 3, 3, 1} 이와 같이 됩니다.

// code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace::std;
 
const int N=300000;
int n;
vector<int> adj[N+5];
bool visit[N+5];
 
int an;        // arr의 길이
int arr[N+5];  // 트리를 펼친 배열
int st[N+5];   // st[x] = (arr[i] == x)인 최소 i
int en[N+5];   // en[x] = (arr[i] == x)인 최대 i
 
void dfs(int now){
    visit[now] = true;
    arr[++an] = now;
    st[now] = an;
    for(auto next: adj[now]){
        if(!visit[next]){
            dfs(next);
        }
    }
    arr[++an] = now;
    en[now] = an;
}
 
void add_edge(int v1,int v2){
    adj[v1].push_back(v2);
    adj[v2].push_back(v1);
}

이런 식으로 트리를 펼치면 트리에서의 쿼리를 배열에서의 구간 쿼리로 바꿀 수 있습니다.

3. Mo's algorithm 의 적용

arr[] = 트리를 펼친 배열 = 위의 예시에선 {1, 2, 5, 5, 4, 4, 2, 3, 3, 1}

start(X) = X 노드가 arr[] 에 처음 등장한 인덱스

end(X) = X 노드가 arr[] 에 마지막으로 등장한 인덱스

 편의 상 arr, start, end 를 위와 같이 정의하겠습니다.

(1) 쿼리로 노드 X 의 subtree 를 처리해야 하는 경우 - 문제 항목 (1) 번의 예

arr[ start(X) ~ end(X) ] 안에 한 번이라도 등장한 노드들은 모두 X의 subtree 내부의 노드들입니다.

arr[ start(X) ~ end(X) ] 안에 한 번도 등장하지 않은 노드들은 모두 X의 subtree 외부의 노드들입니다.

 이는 arr 의 생성과정을 통해 쉽게 증명할 수 있습니다. 그러므로 ( 노드 Y가 노드 X의 subtree에 속해 있다.) 와 (노드 Y가 arr[start(X) ~end(X)] 에 등장한다.) 가 서로 동치입니다. 이를 통해 '트리에서의 쿼리 X' 를 'arr 에서의 쿼리 [ start(X), end(X) ]' 로 바꾼 후 Mo's algorithm을 적용할 수 있습니다.

COUNT[i] = 현재까지 처리된 구간에서 i 노드가 등장한 횟수.

 위와 같은 배열을 저장하면, [start(Xi), end(Xi)] -> [start(X(i+1)), end(X(i+1))] 로 가는 과정에서 어떤 노드들이 삭제되고 추가되는지 알 수 있기 때문입니다. 방법은 모스 알고리즘에서 설명한 것과 동일합니다.

 문제 (1) 번을 이를 활용해 풀 수 있습니다.

(2) 쿼리로 노드 X 와 노드 Y 사이의 경로를 처리해야 하는 경우 - 문제 항목 (0) 번의 예

 P=LCA(X,Y), 그리고 start(X) < start(Y) 라고 하겠습니다. ( start(X) > start(Y) 이면 swap 하면 되기 때문에 일반성을 잃지 않습니다.)

(2) - 1) P==X 인 경우

 ( 노드 Z가 노드 X와 Y의 경로 상에 있다.) 와 (노드 Z가 arr[start(X) ~start(Y)] 에 1번 등장한다.) 가 동치입니다. arr 의 생성과정을 통해 증명할 수 있습니다. (경로 상에 있으면 1번 이상 등장하며, 경로 상에 없으면서 arr[start(X) ~start(Y)]에 등장하는 노드는 2번 등장하게 되기 때문입니다.)

 그러므로 쿼리를 [ start(X), start(Y) ]로 바꿀 수 있습니다.

(2) - 2) P!=X 인 경우

 위와 비슷한 원리로 arr[end(X) ~start(Y)] 에 1번 등장하는 노드들은 모두 경로 상에 있습니다. DFS 과정을 생각해 보면 예외적으로 P 혼자 arr[end(X) ~start(Y)]에 등장하지 않음을 알 수 있지요. 그러므로 쿼리를 [ end(X), start(Y) ] 로 진행한 후, COUNT에 P를 추가적으로 넣어서 계산을 마치고, 이 후 P를 빼면 됩니다.

 문제 (0) 번을 이를 활용해 풀 수 있습니다.

4. 문제

(0) [BOJ 13518] 트리와 쿼리 9

풀이 링크

(1) [CF 221 D] Tree and Queries

※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.

※ 문의 : rikang93@gmail.com