티스토리 뷰
Table of Contents
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} 이와 같이 됩니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | // 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); } | cs |
이런 식으로 트리를 펼치면 트리에서의 쿼리를 배열에서의 구간 쿼리로 바꿀 수 있습니다.
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. 문제
(1) [CF 221 D] Tree and Queries
※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.
※ 문의 : rikang93@gmail.com
'범위 쿼리 처리 ( Range Query )' 카테고리의 다른 글
스파스 테이블 ( Sparse table ) (0) | 2017.11.02 |
---|---|
모스 알고리즘 ( Mo's algorithm ) (0) | 2017.11.02 |