Fragmented Tree
Codeforces를 돌아다니다가 흥미로운 글을 하나 읽었다. Sqrt Fragmented Tree라는 자료구조로, 글 자체는 7년 전의 것이지만 한국에서 잘 알려지지 않았기에 설명하는 글을 작성한다.
Approach
업데이트가 있는 트리 DP는 Centroid Decomposition Tree나, Euler Tour Trick과 HLD를 사용한 소위 Dynamic Tree DP등을 통해서 할 수 있음이 알려져 있다. 물론, 이러한 자료구조들은 구현이 어렵고, 최소한의 생각을 해야 문제가 풀리기 때문에 머리가 아프다.
트리에서 Square Root Decomposition을 사용할 수 있을까라는 생각을 해본 적이 있을 것이다. 트리는 connected component로 나누면 component의 크기 또는 개수 중에 하나는 너무 커지게 된다. 트리를 잘 분할하려면 어떻게 해야할까? 'Connected' component를 포기하면 된다.
Fragmented Tree
Sqrt Fragmented Tree는 위의 고민을 해결하기 위한 자료구조이다. 정점들을 connected component 조건을 포기하고 sqrt개씩 버킷으로 나누려고 한다. 이 버킷을 Fragment라고 한다.
그냥 막 나누면 관리가 너무 어려우니깐, Fragment 내의 각 connected component에 대해서 제일 깊이가 얕은 정점들의 부모가 전부 동일하도록 하면 관리가 좀 더 편할 것이다. 그 부모 정점을 'Fragment의 부모' 정점이라고 하자.
DFS를 통해 Fragment를 형성한다. Fragment를 만드는 방법은 다음과 같다:
1. 각 정점마다 일단 자식으로 향하는 DFS를 도는 것으로 서브트리의 크기를 계산한다.
2. 현재 정점을 부모로 하는 Fragment 후보 집합을 만든다. 현재 정점을 포함하지 않음에 주의하자.
3. 각 자식쪽 서브트리마다 Fragment에 추가되지 않은 정점 집합을 현재 정점의 집합에 추가해준다. 현재 정점의 집합 크기가 sqrt를 넘을 때마다 이 집합으로 이루어진 Fragment를 만들어주고, 집합을 비워준다.
4. 트리의 루트는 아무 Fragment에도 속하지 않기 때문에, 트리의 루트를 포함해서 현재 아무 Fragment에도 속하지 않은 정점들을 가지고 마지막 Fragment를 만들어준다.
각 Fragment의 크기는 sqrt 이상 2*sqrt 미만일 것이다. Fragment 후보 집합의 크기가 sqrt가 넘어갈때만 Fragment를 형성하고 Fragment를 비워주기 때문에, 해당 집합이 sqrt보다 살짝 작은 크기일 때 마찬가지로 sqrt보다 살짝 작은 크기의 집합을 합쳐주게 된다면 2*sqrt에 근접할 수 밖에 없다. 이는 상수 면에서 아쉬운 부분이다.
Fragment를 만들때는 가상의 노드를 새로 하나 더 만들어주면 편리하다. 원래 트리의 각 노드들에 대해서, 이 노드가 어떤 Fragment에 속해 있는지 역추적하는 배열도 만들어주면 편리하다. 또한, Fragment 간의 인접 리스트도 만들어 두면 계산 쿼리를 처리할 때 편리하다.
구현은 다음과 같다. 구현이 짧은 편은 아니지만, 템플릿으로 만들어 두면 쓰기 편할 것으로 예상한다.
int makeNode(int u, const vector<int> &im) {
fragPos.push_back(-1);
fragPar.push_back(u);
dep.push_back(u<0?0:dep[u]+1);
int num=adj.size();
adj.push_back(im);
return num;
}
void makeFragment(int u, Fragment &fr) {
if (fragPos[u]!=-1) return ;
fragPos[u]=frags.size()-1;
fr.add(u);
for (int v:adj[u]) makeFragment(v, fr);
}
void build(int rt=1) {
dep=vector<int>(n+1);
{
queue<array<int, 2>> q;
q.push({rt, -1});
while (q.size()) {
auto [u, p]=q.front();
q.pop();
for (int v:org[u]) if (v!=p) q.push({v, u}), dep[v]=dep[u]+1;
}
}
fragPos=fragPar=vector<int>(n+1, -1);
adj=org;
vector<int> ord(n);
iota(ord.begin(), ord.end(), 1);
sort(ord.begin(), ord.end(), [&](int x, int y) {
return dep[x]>dep[y];
});
vector<int> sz(n+1);
for (int u:ord) {
sz[u]=1;
int sum=0;
vector<int> im, ch;
for (int v:adj[u]) if (dep[u]<dep[v]) sz[u]+=sz[v];
for (int v:adj[u]) if (dep[u]<dep[v]) {
sum+=sz[v];
im.push_back(v);
if (sum>SQ) {
int nd=makeNode(u, im);
im.clear();
ch.push_back(nd);
frags.emplace_back(nd, n);
makeFragment(nd, frags.back());
sz[u]-=sum;
sum=0;
}
}
adj[u]=im;
for (int i:ch) adj[u].push_back(i);
}
int nd=makeNode(-1, vector<int>({rt}));
frags.emplace_back(nd, n);
makeFragment(nd, frags.back());
subAdj=vector<vector<int>>(frags.size());
for (int i=0; auto &fr:frags) {
fr.init();
if (fragPar[fr.t]==-1) continue;
fr.p=fragPos[fragPar[fr.t]];
subAdj[fr.p].push_back(i);
i++;
}
}
업데이트 및 쿼리
Fragment 내부에서의 업데이트를 Naive하게 해주면 $O(\sqrt{n})$이다.
모든 Fragment들을 DFS로 순회하면 마찬가지로 $O(\sqrt{n})$이다. 서브트리 쿼리가 들어온 경우, 서브트리의 루트 정점에서부터 시작해서 내려가는 DFS를 원본 트리에서 돌리고, 다른 Fragment를 만나게 된다면 Fragment간의 DFS를 돌려준다. 이 또한 각 Fragment의 크기가 $O(\sqrt{n})$이기 때문에, $O(\sqrt{n})$이다.
자세한 구현은 밑에 첨부하는 코드를 참고하자. 추가적인 응용은 독자에게 맡긴다.
https://github.com/dsstar-codes/Problem-Solving/blob/master/Library/FragmentedTree.cpp
연습 문제
Naive가 Tree DP로 $O(N)$에 풀리는 문제이고, 제한이 $O(Q\sqrt{N})$이 동작하는 제한이라면 웬만하면 풀 수 있을 것으로 예상한다.
2015 CodeCraft - Queries on the Tree (구현에 어려움이 있다면, 코드는 이 링크를 참고하자.)
Singapore NOI 2022 - Grapevine
BOJ 13515 - 트리와 쿼리 6
SNUPC 2021 - 누텔라 트리 (Hard)
BOJ 13516 - 트리와 쿼리 7
JOI Open Contest 2018 - Cats or Dogs (굉장히 트리키한 구현을 요구한다. HLD를 이용한 풀이가 훨씬 쉽고 간편할 것이다.)