ACMLib

Центроид дерева

June 12, 2017

Определение

Центроидом дерева называется такая вершина $v$, что если подвесить дерево за эту вершину, то размер поддеревьев всех её сыновей будет не больше $n/2$.

Покажем, что в любом дереве есть хотя бы один центроид, и их не больше двух.

Существование

Построим контруктивный алгоритм, который за $O(n)$ находит какой-то центроид.

Подвесим дерево за произвольную вершину и насчитаем размеры поддеревьев с помощью DFS. Теперь встанем в корень и будем идти в наибольшего сына до тех пор, пока его размер строго больше $n/2$.

Утверждается, что вершина $v$, в которой мы остановились, и является центроидом. Все сыновья $v$ действительно имеют размер не более $n/2$. А если это не корень, то сверху осталось не более $n - sz[v] < n/2$ вершин.

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
const int N = 100100;
vector<int> g[N];
int sz[N];

void dfs(int v)
{
	sz[v] = 1;
	for (int u : g[v]) {
		if (sz[u] != 0) continue;
		dfs(u);
		sz[v] += sz[u];
	}
}

int getCentroid(int v) //v - any vertex of tree
{
	dfs(v);
	while(true) {
		int w = -1;
		for (int u : g[v]) {
			if (sz[u] > sz[v]) continue;
			if (2 * sz[u] >= n) {
				w = u;
				break;
			}
		}
		if (w == -1) break;
		v = w;
	}
	return v;
}

Ограничение сверху

Какой-то центроид $v$ у нас уже есть. Подвесим дерево за него. Другим центроидом может быть только вершина $u$ такая, что размер её поддерева не меньше $n/2$, иначе сверху от неё будет строго больше $n/2$ вершин. Но размер поддеревьев сыновей $v$ не больше $n/2$ по определению центроида. Следовательно, другим центроидом может быть только сын $v$ с размером поддерева ровно $n/2$. Но у $v$ не может быть больше одного такого сына, потому что иначе размер всего дерева был бы не менее $n/2 + n/2 + 1 > n$.

Можно заметить, что в нашем алгоритме искомый сын $v$ может быть только ниже $v$, так как количество вершин сверху строго меньше $n/2$.

Код

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
35
36
37
38
39
40
41
42
43
const int N = 100100;
vector<int> g[N];
int sz[N];

void dfs(int v)
{
	sz[v] = 1;
	for (int u : g[v]) {
		if (sz[u] != 0) continue;
		dfs(u);
		sz[v] += sz[u];
	}
}

int getCentroid(int v) //v - any vertex of tree
{
	dfs(v);
	while(true) {
		int w = -1;
		for (int u : g[v]) {
			if (sz[u] > sz[v]) continue;
			if (2 * sz[u] >= n) {
				w = u;
				break;
			}
		}
		if (w == -1) break;
		v = w;
	}
	return v;
}

vector<int> getCentroids(int v) //v - any vertex of tree
{
	v = getCentroid(v);
	vector<int> res;
	res.push_back(v);
	for (int u : g[v]) {
		if (2 * sz[u] == n)
			res.push_back(u);
	}
	return res;
}