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를 이용한 풀이가 훨씬 쉽고 간편할 것이다.)