Разбор

Пусть имеется дерево из $n$ вершин.

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

В задаче следует найти все центроиды дерева.

Рассмотрим примеры деревьев и их центроиды (отмечены зеленым цветом).

Запустим поиск в глубину $df s (v)$ , который в $s u b [v]$ вычислит количество вершин в поддереве с вершиной $v$ . Для приведенных примеров возле каждой вершины $v$ укажем соответствующее ей значение $s u b [v]$ (поиск в глубину стартуем во всех примерах из вершины $1$ ).

Если вершина $v$ имеет сыновей $t o_{1}, t o_{2}, ..., t o_{k}$ , то

s u b_{v} = 1 + s u b_{t o_{1}} + s u b_{t o_{2}} + ... + s u b_{t o_{k}}

Вершина $v$ является центроидом дерева тогда и только тогда, когда:

для каждого ее сына $t o$ имеет место $s u b [t o] \leq n /2$ ;
если из дерева удалить поддерево с корнем $v$ , то оно будет содержать не более $n /2$ вершин: $n - s u b [v] \leq n /2$ ;

Например, в правом на рисунке дереве с $n = 5$ вершинами центроидом будет вершина $2$ , потому что

$s u b [4] = 2 \leq n /2$ ;
$s u b [3] = 1 \leq n /2$ ;
$n - s u b [2] = 5 - 4 = 1 \leq n /2$ ;

Пример

Рассмотрим дерево из примера. Вершина $6$ является центроидом.

Реализация алгоритма

Граф будем хранить в списке смежности $g$ .

vector<vector<int> > g;

Функция dfs возвращает количество вершин в поддереве с вершиной $v$ и сохраняет это значение в $s u b [v]$ .

int dfs(int v, int p = -1)
{
  sub[v] = 1;
  for (int to : g[v])
    if (to != p) sub[v] += dfs(to, v);
  return sub[v];
}

Функция centroid совершает поиск в глубину, находит и заносит центроиды в массив $ce n t r$ .

void centroid(int v, int p = -1)
{

Установим $f l a g = 1$ , если вершина $v$ является центроидом.

  int flag = 1;

Перебираем вершины $t o$ , смежные с $v$ . Рассматриваем ребро $v \to t o$ .

  for (int to : g[v])
    if (to != p)
    {

Если для сына $t o$ выполняется $s u b [t o] > n /2$ , то $v$ не является центроидом.

      if (sub[to] > n / 2) flag = 0;

Если для сына $t o$ выполняется $s u b [t o] < n /2$ , то в поддереве с корнем $t o$ не содержится центроидов. Есть смысл продолжать поиск в сыне $t o$ , если только $s u b [t o] \geq n /2$ .

      if (sub[to] >= n / 2) centroid(to, v);
    }

Дерево без поддерева с корнем $v$ содержит $n - s u b [v]$ вершин. Если оно содержит более $n /2$ вершин, то $v$ не центроид.

  if (n - sub[v] > n / 2) flag = 0;

Если для вершины $v$ выполняются все условия центроида, то заносим ее в массив $ce n t r$ .

  if (flag) centr.push_back(v);
}

Основная часть программы. Инициализируем массивы.

scanf("%d", &n);
g.resize(n + 1);
sub.resize(n + 1);

Читаем входной граф.

for (i = 0; i < n - 1; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

Запускаем поиск в глубину, ищем центроиды дерева.

dfs(1);
centroid(1);

Выводим один из центроидов.

printf("%d\n", centr[0]);

Реализация алгоритма — второе решение

Запустим поиск в глубину $df s (v)$ , который для каждой вершины $v$ вычислит следующие величины:

$s u b [v]$ содержит количество вершин в поддереве с вершиной $v$ ;
$f [v]$ содержит максимальный размер поддерева среди всех поддеревьев вершины $v$ , включая поддерево, содержащее родительскую вершину $v$ .

Тогда центроидом будет вершина $v$ с наименьшим значением $f [v]$ . Таких вершин может быть либо одна либо две в дереве.

Вершина $v = 6$ соединена с $4$ поддеревьями, размер которых соответственно равен $1, 2, 3$ и $5$ . Значение $f [6] = 5$ содержит максимальный размер поддерева.

В то же время наименьшим значением в массиве $f$ является $f [6] = 5$ . Следовательно вершина $6$ является центроидом.

Рассмотрим расстановку меток для дерева с двумя центроидами.

Две вершины имеют наименьшее значение в массиве $f$ : $f [1] = 3$ и $f [2] = 3$ .

void dfs(int v, int p = -1)
{
  sub[v] = 1;
  f[v] = 0;
  for (int to : g[v])
    if (to != p)
    {
      dfs(to, v);
      sub[v] += sub[to];
      f[v] = max(f[v], sub[to]);
    }
  f[v] = max(f[v], n - sub[v]);
  if ((root == 0) || (f[v] < f[root])) root = v;
}

Основная часть программы. Читаем входные данные. Инициализируем массивы.

scanf("%d", &n);
g.resize(n + 1);
f.resize(n + 1);
sub.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

Запускаем поиск в глубину, выводим один из центроидов дерева root.

root = 0;
dfs(1);
printf("%d\n", root);

Python реализация

Увеличим размер стека.

import sys
sys.setrecursionlimit(300000)

Функция dfs возвращает количество вершин в поддереве с вершиной $v$ и сохраняет это значение в $s u b [v]$ .

def dfs(v, p = -1):
  sub[v] = 1
  for to in g[v]:
    if to != p:
      sub[v] += dfs(to, v)
  return sub[v]

Функция centroid совершает поиск в глубину, находит и заносит центроиды в массив $ce n t r$ .

def find_centroid(v, p = -1):

Установим $f l a g = T r u e$ , если вершина $v$ является центроидом.

  flag = True

Перебираем вершины $t o$ , смежные с $v$ . Рассматриваем ребро $v \to t o$ .

  for to in g[v]:
    if to == p: continue

Если для сына $t o$ выполняется $s u b [t o] > n /2$ , то $v$ не является центроидом.

    if sub[to] > n // 2:
      flag = False

    if sub[to] >= n // 2:
      find_centroid(to, v)

  if n - sub[v] > n // 2:
      flag = False

Если для вершины $v$ выполняются все условия центроида, то заносим ее в массив $ce n t r$ .

  if flag: centr.append(v)

Основная часть программы. Читаем входные данные. Инициализируем массивы.

n = int(input())
g = [[] for _ in range(n + 1)]
sub = [0] * (n + 1)
centr = []

Читаем входной граф.

for i in range(n - 1):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

Запускаем поиск в глубину, ищем центроиды дерева.

dfs(1)
find_centroid(1)

Выводим один из центроидов.

print(centr[0])

Python реализация — второе решение

Увеличим размер стека.

import sys
sys.setrecursionlimit(200000)

Запустим поиск в глубину $df s (v)$ , который для каждой вершины $v$ вычислит следующие величины:

$s u b [v]$ содержит количество вершин в поддереве с вершиной $v$ ;
$f [v]$ содержит максимальный размер поддерева среди всех поддеревьев вершины $v$ , включая поддерево, содержащее родительскую вершину $v$ .

def dfs(v, p=-1):
  global root
  sub[v] = 1
  f[v] = 0
  for to in g[v]:
    if to != p:
      dfs(to, v)
      sub[v] += sub[to]
      f[v] = max(f[v], sub[to])
  f[v] = max(f[v], n - sub[v])
  if root == 0 or f[v] < f[root]:
    root = v

Основная часть программы. Читаем входные данные. Инициализируем массивы.

n = int(input())
g = [[] for _ in range(n + 1)]
f = [0] * (n + 1)
sub = [0] * (n + 1)

for _ in range(n - 1):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

Запускаем поиск в глубину, выводим один из центроидов дерева root.

root = 0
dfs(1)
print(root)