XOR MST

다음과 같은 완전 그래프를 생각해 보자.

그래프의 정점은 $V$개이다. 각 정점에는 0 이상의 정수 가중치가 붙어 있다. 간선의 가중치는 간선이 잇고 있는 두 정점의 가중치의 XOR 값이다.

# 는 이 그래프의 MST를 구하는 문제이다.

이 문제는 cs71107님의 XOR 관련 문제를 푸는 접근법들에도 나왔듯 자릿수가 큰 비트부터 내려가면서 일종의 그리디 알고리즘을 사용하게 된다.

가중치의 범위가 $2^{30}$이므로, 30번째 비트부터 생각해 보자. 어떤 정점의 가중치는 $2^{30}$ 미만일 것이고, 어떤 정점의 가중치는 $2^{30}$ 이상일 것이다. 가중치가 $2^{30}$ 미만인 두 정점을 잇는 간선의 가중치는 물론 $2^{30}$ 보다 작을 것이다. 가중치가 $2^{30}$ 이상인 두 정점을 잇는 간선의 가중치 또한 $2^{30}$ 보다 작을 것이다. 마지막으로, 가중치가 $2^{30}$ 이상인 정점과 $2^{30}$ 미만인 정점을 잇는 간선의 가중치는 $2^{30}$ 이상일 것이다. 이들을 종합하면 다음과 같은 관찰을 할 수 있다.

가중치가 $2^{30}$ 보다 작은 간선들만 남긴 부분 그래프는 정확히 다음과 같은 두 개의 컴포넌트로 이루어진 그래프이다.

가중치가 $2^{30}$ 이상인 정점들
가중치가 $2^{30}$ 미만인 정점들

따라서, 각 부분 그래프의 MST를 구한 다음, 하나의 간선을 더 그으면 전체 그래프의 MST를 만들 수 있다는 관찰로 이어진다. 분할 정복 알고리즘으로 해결하기 위해서는, 사실은 가장 어려운 문제인, 더 그으면 되는 하나의 간선을 어떻게 찾을 것인가 를 빠른 시간 안에 해결해야 한다.

이는 0 이상의 정수들로 이루어진 두 집합에서 원소를 하나씩 골라, XOR한 값을 최소화하는 문제와 같다. 두 집합 중 하나를 쿼리로 생각하는 발상으로, 다음과 같은 두 쿼리를 빠르게 처리하는 문제로 생각할 수 있게 된다.

$update(x)$: 집합 $S$에 수 $x$를 추가한다.
$query(x)$: 집합 $S$에서, 수 $x$와 XOR한 결과가 가장 작은 수를 구한다. $S$가 비어있지 않다고 가정한다.

이는 크기 $2^{30}$ (수 $x$의 범위만큼 만들어야 한다) 의 세그먼트 트리를 만들어서 해결할 수 있다. 동적 세그먼트 트리를 사용하면, 수의 개수는 $V$개 이하이므로 세그먼트 트리는 $O(V \log {2^{30}})$ 의 시간에 작동한다. 분할 정복 과정에서 각 부분 트리에 대한 세그먼트 트리를 재사용할 수 있으며, 소스 코드는 아래와 같다.

#include <bits/stdc++.h>
using namespace std;

using lint = long long;

const int maxn = 200004;
int N;
vector<int> a;

struct tree {
	int t[maxn*32], l[maxn*32], r[maxn*32], K = 2;

	void update(int s, int e, int x, int p, int v) {
		if (s == e) t[x] += v;
		else {
			int m = (s+e) / 2;
			if (!l[x]) l[x] = K++;
			if (!r[x]) r[x] = K++;
			if (p <= m) update(s, m, l[x], p, v);
			else update(m+1, e, r[x], p, v);
			t[x] = t[l[x]] + t[r[x]];
		}
	}
	void update(int p, int v) { return update(0, (1<<30)-1, 1, p, v); }

	int query(int d, int s, int e, int x, int p) {
		if (s == e) return s;
		else {
			int m = (s+e) / 2;

			if ((p >> d) & 1) {
				if (r[x] and t[r[x]]) return query(d-1, m+1, e, r[x], p);
				else return query(d-1, s, m, l[x], p);
			} else {
				if (l[x] and t[l[x]]) return query(d-1, s, m, l[x], p);
				else return query(d-1, m+1, e, r[x], p);
			}
		}
	}
	int query(int p) { return query(29, 0, (1<<30)-1, 1, p); }
} t;

lint f(vector<int> v, int d) {
	if (d < 0 || v.empty()) return 0;

	vector<int> l, r;

	for (int x : v) {
		if ((x >> d) & 1) r.push_back(x);
		else l.push_back(x);
	}

	int now = 2e9;

	if (l.empty() || r.empty()) now = 0;
	else {
		for (int x : l) t.update(x, 1);
		for (int x : r) {
			x ^= 1 << d;
			now = min(now, t.query(x) ^ x);
		}
		for (int x : l) t.update(x, -1);
		now += 1 << d;
	}

	return f(l, d-1) + f(r, d-1) + now;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> N;
	for (int i=0; i<N; i++) {
		int x;
		cin >> x;
		a.push_back(x);
	}

	cout << f(a, 29) << '\n';
}

XOR에서 흔히 나오는 기법을 적절히 사용하는 좋은 문제이다.

XOR MST의 역

느닷없이 XOR MST와 이의 풀이를 소개한 이유는, 문제 자체도 좋은 문제지만, 이의 역 문제가 정의 가능하고, 재미있는 조건 아래에서만 풀 수 있기 때문이다. XOR MST의 역문제는 다음과 같이 정의될 것이다.

정점이 $V$개인 트리가 주어진다. XOR MST 문제와 같이 정의된 그래프가 이 트리를 MST로 가지도록, 그래프의 정점의 가중치를 부여하여라.

XOR MST 문제에서 정점의 가중치가 $2^{30}$ 미만이었으므로, 정점에 부여되는 가중치가 $2^{30}$ 미만이어야 한다는 조건 또한 덧붙이도록 하자. XOR MST 문제를 풀었다면, 이 역문제도 다음과 같은 발상으로 해결하고 싶을 것이다.

트리를 두 컴포넌트로 쪼갠다.
쪼갠 두 컴포넌트의 정점에 $2^{29}$ 미만의 가중치를 부여한다.
둘 중 한 컴포넌트의 가중치에 일괄적으로 $2^{29}$ 을 더한다.
마지막으로, 두 컴포넌트를 잇는 간선을, 1.에서 쪼갠 두 컴포넌트를 잇는 간선이 되게 한다. 이는 간선의 양쪽 정점에 각각 $0$, $2^{29}$ 의 가중치가 부여되도록 컴포넌트 전체에 적절한 값을 XOR해주면 된다. 트리의 모든 정점에 동일한 값을 XOR하여도 각 간선의 가중치는 동일하며, 따라서 MST도 동일하다는 사실을 이용한다.

문제는, 트리가 비슷한 크기로 쪼개지도록 하는 간선이 없을 수도 있다는 것이다. 극단적으로, 2번부터 $N$ 번까지의 모든 정점이 1번 정점과 연결되어 있는 별 모양 그래프 (star graph)라면 어떤 간선으로 그래프를 쪼개도 정점 1개와 $N-1$개가 있는 컴포넌트로 쪼개질 수밖에 없다. 이러한 그래프는 차수가 아주 높은 정점 하나가 존재한다는 것이다. 만일 ‘차수가 아주 높은 정점’이 존재하지 않고 모든 정점의 차수가 아주 낮은 수라면 문제를 풀 수 있을까?

이러한 발상에서 만든 문제가 BOJ 20503. Haven 이다. 이 문제에서는 모든 정점의 가중치가 3 이하라는 조건을 넣었다. 이 조건은 흔히 트리가 이진 트리임을 우회적으로 표현하는 방법이기 때문에, 이진 트리(특히 균형잡힌 이진 트리)에서 사용할 수 있는 알고리즘들을 활용하려 할 수 있다. 그하지만 그러한 알고리즘들은 문제의 풀이와 큰 관련이 없고, 단지 그래프가 성기게 연결되어 있다는 점만이 중요하다.

정리. 트리의 각 정점의 차수가 3 이하일 때, 간선을 잘랐을 때 두 컴포넌트의 크기 $S_1$, $S_2$가 $S_2 \le 2 S_1 + 1$, $S_1 \le 2S_2 + 1$ 을 만족하도록 하는 간선이 존재한다. 즉, 두 컴포넌트의 크기가 각각 $V/3$ 이상이 되는 간선을 찾을 수 있다.

증명. 센트로이드의 존재성과 비슷한 방법으로, 어떠한 간선도 이 조건을 만족하지 않는다(‘균형잡혀있지 않다’고 부르기로 하자)고 가정하고 모순을 이끌어낼 수 있다. 이와 같이 ‘균형잡혀있지 않은’ 간선 두 개 or 세 개와 연결되어 있는 정점을 생각하면, 모두 각기의 이유로 존재성이 부정당하게 된다.

따라서 이 문제에서는 해당 발상을 적용할 수 있게 되며, 아래와 같은 코드로 문제를 해결할 수 있게 된다.

#include <bits/stdc++.h>
using namespace std;

using lint = long long;

const int maxn = 200004;

int N, prt[maxn], sz[maxn];
vector<int> g[maxn];
lint ans[maxn];

void remove(vector<int> &v, int x) {
	for (int i=0; i<v.size(); i++) if (v[i] == x) {
		if (i+1 != v.size()) swap(v[i], v[v.size()-1]);
		v.pop_back();
		break;
	}
}

void dfs(int x, int p, vector<int> &v) {
	v.push_back(x);
	prt[x] = p;
	sz[x] = 1;

	for (int y : g[x]) if (y != p) {
		dfs(y, x, v);
		sz[x] += sz[y];
	}
}


void solve(int s, int d) {
	vector<int> v, vx;

	dfs(s, s, v);

	int mx = -1, X;
	for (int x : v) if (prt[x] != x) {
		int now = min(sz[x], (int)v.size()-sz[x]);
		if (now > mx) {
			mx = now;
			X = x;
		}
	}

	if (mx >= 0) {
		int Y = prt[X];


		remove(g[X], Y);
		remove(g[Y], X);
		dfs(X, X, vx);
		solve(X, d-1);
		solve(Y, d-1);

		int ansX = (1ll << d) ^ ans[X] ^ ans[Y];
		for (int x : vx) ans[x] ^= ansX;
	}
}

int main() {
	cin >> N;
	for (int i=1; i<N; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}

	solve(1, 28);

	for (int i=1; i<=N; i++) {
		cout << ans[i];
		if (i < N) cout << ' ';
	}

	cout << '\n';
}

이 덕분에, 문제와 같이 정점이 20만 개인 트리에서 28단계의 분할정복 안에 문제를 해결할 수 있게 된다. 하지만 실제로 이는 꽤나 성긴 제한으로, 실제로 26단계 초과가 소요되는 트리는 찾을 수 없다. 최악의 경우는 다음과 같이 피보나치 비율로 만들어지는 이진 트리이다.

트리 $T(V)$는 정점의 개수가 $V$개인 이진 트리이다.
$V=0$인 경우, $T(V)$는 빈 트리이다. $V=1$인 경우, $T(V)$는 정점 하나로 이루어진 트리이다.
$T$의 루트 정점의 왼쪽 자식은 $T(\lfloor V/\rho \rfloor)$, 오른쪽 자식은 $T(V - \lfloor V / \rho \rfloor)$ 이다. 이 때, $\rho = (1 + \sqrt 5) / 2$ 이다.

이와 같이 트리의 최대 차수는 트리가 성기게 연결되어 있는 척도 중 하나로 생각할 수 있으며, 이는 다양한 방향으로 확장할 수 있다. 이에 대해서는 후속 글에서 서술한다.

XOR MST

XOR MST

XOR MST의 역

Faster Exponential Algorithm for Permutation Pattern Matching

알고리즘 문제 접근 과정 7