•Статьи•3 месяца назад

Деревья

Деревья — одна из ключевых структур данных в алгоритмах, и они встречаются в широком спектре задач.

Дерево — это связный ацикличный неориентированный граф.

Граф $G = (V, E)$ называется деревом, если он:

Связный — в графе существует путь между любой парой вершин.
Ацикличный — граф не содержит циклов.

В дереве с $n$ вершинами всегда ровно $n - 1$ ребро.

Основные свойства дерева

1. Связность и единственность путей

В дереве существует единственный путь между любой парой вершин.

2. Количество рёбер

Для любого дерева:

∣ E ∣ = ∣ V ∣ - 1

3. Нет циклов

Добавление хотя бы одного ребра в дерево всегда образует цикл.

4. Корень (для корневого дерева)

Если выбрать одну вершину как корень, дерево становится направленным от корня к потомкам. Это используется при рекурсивных обходах и алгоритмах ( $D FS$ , $L C A$ и т.д.).

5. Поддеревья

Любая вершина с её потомками образует поддерево. Оно само по себе является деревом.

6. Листья

Вершины с нулём детей (в корневом дереве) называются листьями.

7. Глубина и высота

Глубина вершины — расстояние от корня до этой вершины.
Высота дерева — максимальная глубина среди всех вершин.

8. Центр дерева

Центр — вершина (или пара соседних вершин), минимизирующая максимальное расстояние до всех остальных.

Альтернативные определения дерева

Следующие определения дерева эквивалентны и могут использоваться в разных контекстах:

Граф без циклов, который становится несвязным при удалении любого ребра.
Связный граф с $n$ вершинами и $n - 1$ ребром.
Ацикличный граф с $n - 1$ рёбрами, у которого есть ровно одна компонента связности.

Представление деревьев в коде

В зависимости от задачи и типа дерева (общего, бинарного, корневого и т.д.) используются разные структуры данных:

1. Списки смежности

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

int n;
vector<vector<int>> tree(n); // дерево из n вершин

// добавление ребра между вершинами u и v
tree[u].push_back(v);
tree[v].push_back(u); // если дерево неориентированное

2. Массив родителей

Очень компактное представление, особенно если дерево уже построено.

vector<int> parent(n); // parent[i] — родитель вершины i
// если i — корень, то обычно parent[i] = -1 или 0

3. Указатели / структуры (ООП стиль)

Часто используется при построении бинарных деревьев, бора, декораторов, особенно в Python/Java/C++ с ООП.

Бинарное дерево:

struct Node 
{
  int val;
  Node* left;
  Node* right;
  Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Общее дерево:

struct Node 
{
  int val;
  vector<Node*> children;
  Node(int v) : val(v) {}
};

Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определите, является ли этот граф деревом.

Вход. Первая строка содержит количество вершин графа $n (1 \leq n \leq 100)$ . Далее записана матрица смежности размером $n \times n$ , в которой $1$ обозначает наличие ребра, $0$ — его отсутствие. Матрица симметрична относительно главной диагонали.

Выход. Выведите сообщение "YES", если граф является деревом, и "NO" в противном случае.

Открыть задачу

Граф из $n$ вершин является деревом тогда и только тогда, когда:

Граф связный. Запустим поиск в глубину из первой вершины. Подсчитаем количество посещенных вершин в процессе поиска. Если оно равно $n$ , то граф является связным.
$∣ V ∣ = ∣ E ∣ + 1$ . Если граф является деревом, то он содержит $n - 1$ ребро.
Граф не содержит циклов. Запустим поиск в глубину из первой вершины. Если существует обратное ребро, то граф имеет цикл и не является деревом.

Выполнение условий $1)$ и $2)$ или $1)$ и $3)$ достаточно для того, чтобы граф являлся деревом.

Пример

Граф, приведенный в примере, является деревом.

Объявим матрицу смежности графа $g$ и массив $u se d$ .

#define MAX 110
int g[MAX][MAX], used[MAX];

Функция dfs реализует поиск в глубину из вершины $v$ . Предком вершины $v$ является $p$ . Переменная $f l a g$ станет равной $1$ , если будет обнаружен цикл.

void dfs(int v, int p)
{

Если граф уже не является деревом $(f l a g = 1)$ , то нет смысла продолжать поиск.

  if (flag) return;

Отмечаем вершину $v$ как пройденную.

  used[v] = 1;

Посещена вершина $v$ , увеличиваем $c$ на $1$ .

  c++;

Ребро $(v, i)$ будет обратным и образовывать цикл, если $i \neq = p$ и при этом вершина $i$ уже была пройдена $(u se d [i] = 1)$ . В случае обнаружения цикла установим $f l a g = 1$ . Если цикла нет, то продолжаем поиск из вершины $i$ .

  for(int i = 0; i < n; i++)
    if ((i != p) && g[v][i])
      if(used[i]) flag = 1; else dfs(i,v);
}

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

scanf("%d",&n); 
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
  scanf("%d",&g[i][j]);

В переменной $c$ подсчитываем количество посещенных вершин при поиске в глубину. Установим $f l a g = 0$ , если в графе нет цикла. При обнаружении цикла $f l a g$ станет равным $1$ .

c = 0;
flag = 0;

Все вершины изначально являются непройденными (обнуляем массив $u se d$ ).

memset(used,0,sizeof(used));

Запускаем поиск в глубину из нулевой вершины. Поскольку она является корнем дерева поиска, то не имеет родителя. В качестве второго аргумента передаем функции dfs значение $- 1$ .

dfs(0,-1);

Граф не будет деревом, если существует обратное ребро $(f l a g = 1)$ или граф не является связным $(c \neq = n)$ .

if (flag || (c != n)) printf("NO\n"); else printf("YES\n");

Python реализация — проверка условий 1) и 3)

def dfs(v, p):

Объявим глобальные переменные, используемые функцией.

  global flag, c

Если граф уже не является деревом $(f l a g = 1)$ , то нет смысла продолжать поиск.

  if flag: return

Отмечаем вершину $v$ как пройденную.

  used[v] = 1

Посещена вершина $v$ , увеличиваем $c$ на $1$ .

  c += 1

  for i in range(n):
    if i != p and g[v][i]:
      if used[i]: flag = 1
      else: dfs(i, v)

Основная часть программы. Читаем входное значение $n$ .

n = int(input())

c = 0
flag = 0

Все вершины изначально являются непройденными (список $u se d$ заполняем нулями).

used = [0] * n

Создаем матрицу смежности $g$ , изначально заполняем ее нулями.

g = [[0] * n for _ in range(n)]

Читаем входную матрицу смежности.

for i in range(n):
  g[i] = list(map(int, input().split()))

Запускаем поиск в глубину из вершины $0$ .

dfs(0, -1)

Граф не будет деревом, если существует обратное ребро $(f l a g = 1)$ или граф не является связным $(c \neq = n)$ .

if flag or c != n:
  print("NO")
else:
  print("YES")

Объявим матрицу смежности графа $g$ и массив $u se d$ .

#define MAX 101
int g[MAX][MAX], used[MAX];

Функция dfs реализует поиск в глубину из вершины $v$ .

void dfs(int v)
{

Отмечаем вершину $v$ как пройденную.

  used[v] = 1;

Посещена вершина $v$ , увеличиваем $c$ на $1$ .

  c++;

Перебираем вершины $i$ , куда можно двигаться из $v$ . Передвижение из $v$ в $i$ возможно, если:

существует ребро $(v, i)$ , то есть $g [v] [i] = 1$ ;
вершина $i$ еще не пройдена $(u se d [i] = 0)$

Если оба условия верны, то продолжаем поиск в глубину из вершины $i$ .

  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i]) dfs(i);
}

Основная часть программы. Читаем входное значение $n$ .

scanf("%d", &n);

Количество ребер в графе подсчитываем в переменной $E d g es$ .

Edges = 0;

Все вершины изначально являются непройденными (обнуляем массив $u se d$ ).

memset(used, 0, sizeof(used));

Читаем матрицу смежности $g$ . Подсчитываем количество ребер в графе.

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
  scanf("%d", &g[i][j]);
  Edges += g[i][j];
}

Поскольку граф неориентированный, то ребра $(u, v)$ и $(v, u)$ считаются одинаковыми. Разделим значение $E d g es$ на $2$ .

Edges /= 2;

В переменной $c$ подсчитываем количество посещенных вершин при поиске в глубину.

c = 0;

Запускаем поиск в глубину из вершины $1$ .

dfs(1);

Граф является деревом, если количество ребер в нем равно $n - 1$ , а также если он связный $(c = n)$ .

if ((Edges == n - 1) && (c == n)) printf("YES\n");
else printf("NO\n");

Python реализация — проверка условий 1) и 2)

Функция dfs реализует поиск в глубину из вершины $v$ .

def dfs(v):
  global c

Отмечаем вершину $v$ как пройденную.

  used[v] = 1

Посещена вершина $v$ , увеличиваем $c$ на $1$ .

  c += 1

Перебираем вершины $i$ , куда можно двигаться из $v$ . Передвижение из $v$ в $i$ возможно, если:

существует ребро $(v, i)$ , то есть $g [v] [i] = 1$ ;
вершина $i$ еще не пройдена $(u se d [i] = 0)$

Если оба условия верны, то продолжаем поиск в глубину из вершины $i$ .

  for i in range(1, n + 1):
    if g[v][i] and not used[i]: dfs(i)

Основная часть программы. Читаем входное значение $n$ .

n = int(input())

Количество ребер в графе подсчитываем в переменной $E d g es$ .

Edges = 0

Все вершины изначально являются непройденными (список $u se d$ заполняем нулями).

used = [0] * (n + 1)

Создаем матрицу смежности $g$ , изначально заполняем ее нулями.

g = [[0] * (n + 1) for _ in range(n + 1)]

Читаем матрицу смежности $g$ . В переменной $E d g es$ подсчитываем количество ребер в графе.

for i in range(1, n + 1):
  g[i] = [0] + list(map(int, input().split()))
  Edges += sum(g[i])

Поскольку граф неориентированный, то ребра $(u, v)$ и $(v, u)$ считаются одинаковыми. Разделим значение $E d g es$ на $2$ .

Edges //= 2

В переменной $c$ подсчитываем количество посещенных вершин при поиске в глубину.

c = 0

Запускаем поиск в глубину из вершины $1$ .

dfs(1)

Граф является деревом, если количество ребер в нем равно $n - 1$ , а также если он связный $(c = n)$ .

if Edges == n - 1 and c == n:
  print("YES")
else:
  print("NO")

Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево.

Вход. Первая строка содержит два целых числа — количество вершин $n (1 \leq n \leq 100)$ и количество ребер $m$ в графе. Далее следуют $m$ пар целых чисел, каждая из которых задаёт одно ребро. Гарантируется, что граф связный.

Выход. Выведите $n - 1$ пару чисел — ребра, входящие в дерево. Ребра можно выводить в любом порядке.

Открыть задачу

Матрицу смежности графа храним в массиве $g$ .

#define MAX 101
int g[MAX][MAX], used[MAX];

Функция dfs выполняет поиск в глубину, начиная с вершины $v$ . Выводим каждое ребро $(v, i)$ , входящее в дерево поиска в глубину.

void dfs(int v)
{
  used[v] = 1;
  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i])
    {
      printf("%d %d\n",v,i);
      dfs(i);
    }
}

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

scanf("%d %d",&n,&m);
memset(g,0,sizeof(g)); memset(used,0,sizeof(used));
while(m--)
{
  scanf("%d %d",&a,&b);
  g[a][b] = g[b][a] = 1;
}

Запускаем поиск в глубину из первой вершины.

dfs(1);

Задано дерево — простой связный граф без циклов.

Найдите максимальное количество ребер, которое можно удалить из дерева так, чтобы получился лес, в котором каждая компонента связности содержала четное число вершин.

Например, в дереве с $4$ вершинами можно удалить не более $1$ ребра, чтобы получился четный лес.

Вход. Первая строка содержит два целых числа $n (2 \leq n \leq 100, n$ четное) — количество вершин, и $m$ — количество ребер. Каждая из следующих $m$ строк содержит по два целых числа — номера вершин, соединенные ребром. Корнем дерева является вершина $1$ .

Выход. Выведите наибольшее возможное количество удаленных ребер.

Открыть задачу

В задаче следует совершить декомпозицию дерева на компоненты связности с четным числом вершин. При этом следует максимизировать количество этих компонент.

Запустим поиск в глубину из вершины $1$ , которая является корнем дерева. Для каждой вершины $v$ определим количество вершин в поддереве с корнем $v$ . Если это количество четное, то удалим ребро, соединяющее $v$ с его предком при поиске в глубину.

Для корня (вершины $1$ ) размер всего дерева четный. Однако ребра, соединяющего вершину $1$ с ее предком, не существует. Поэтому из результата, полученного по выше приведенному алгоритму, следует вычесть $1$ .

Пример

Рассмотрим дерево, приведенное в примере. Рядом с каждой вершиной указан размер поддерева, если рассматривать эту вершину в качестве корня. Вершины $1, 3$ и $6$ имеют поддеревья с четным количеством вершин. Поскольку вершина $1$ является корнем и не имеет ребра, ведущего к предку, мы удаляем два ребра: $(1, 3)$ и $(1, 6)$ .

Дерево распалось на $3$ компоненты связности, каждая из которых содержит четное количество вершин.

Объявим рабочие массивы.

#define MAX 101
int g[MAX][MAX], used[MAX];

Функция dfs совершает поиск в глубину из вершины $v$ и возвращает количество вершин в поддереве с корнем $v$ .

int dfs(int v)
{
  used[v] = 1;

В переменной $s$ вычисляем количество вершин в поддереве с корнем $v$ .

  int s = 1;

Перебираем сыновей $i$ вершины $v$ . Прибавляем к $s$ значения $df s (i)$ .

  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i]) s += dfs(i);

Если размер поддерева $s$ четный, удаляем ребро между $v$ и его предком.

  if (s % 2 == 0) res++;

Возвращаем количество вершин в поддереве с корнем $v$ .

  return s;
}

Основная часть программы. Читаем входные данные. Строим граф.

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

Запускаем поиск в глубину из вершины $1$ . В переменной $res$ подсчитываем количество удаленных ребер.

res = 0;
dfs(1);

Ребра из $1$ в его предка не существует. Выводим $res - 1$ .

printf("%d\n", res - 1);

Python реализация

Функция dfs совершает поиск в глубину из вершины $v$ и возвращает количество вершин в поддереве с корнем $v$ .

def dfs(v):
  used[v] = 1

В переменной $s$ вычисляем количество вершин в поддереве с корнем $v$ .

  s = 1

Перебираем сыновей $i$ вершины $v$ . Прибавляем к $s$ значения $df s (i)$ .

  for i in range(1, n + 1):
    if g[v][i] and not used[i]:
      s += dfs(i)

Если размер поддерева $s$ четный, удаляем ребро между $v$ и его предком.

  if s % 2 == 0:
    global res
    res += 1

Возвращаем количество вершин в поддереве с корнем $v$ .

  return s

Основная часть программы. Читаем входные данные. Строим граф.

n, m = map(int, input().split())
g = [[0] * (n + 1) for _ in range(n + 1)]
used = [0] * (n + 1)

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

Запускаем поиск в глубину из вершины $1$ . В переменной $res$ подсчитываем количество удаленных ребер.

res = 0
dfs(1)

Ребра из $1$ в его предка не существует. Выводим $res - 1$ .

print(res - 1)

По заданной структуре компании вычислите количество подчиненных для каждого сотрудника.

Вход. В первой строке находится целое число $n (1 \leq n \leq 2 \cdot 1 0^{5})$ — количество сотрудников. Сотрудники пронумерованы числами $1, 2, ..., n$ . Сотрудник $1$ номер является генеральным директором компании.

Далее следуют $n - 1$ целых чисел: для каждого сотрудника $2, 3, ..., n$ указан их непосредственный начальник в компании.

Выход. Выведите $n$ целых чисел. Для каждого сотрудника $1, 2, ..., n$ выведите количество его подчиненных.

Открыть задачу

Структурой компании является дерево. Для каждой вершины дерева $v$ необходимо определить количество вершин $s u m [v]$ в поддереве, где она является корнем. Тогда количество подчиненных у сотрудника $v$ будет равно $s u m [v] - 1$ (поскольку сотрудник $v$ не является собственным подчиненным).

Запустим поиск в глубину из вершины $1$ , которая соответствует генеральному директору компании. Если $t o_{1}, t o_{2}, ..., t o_{k}$ — сыновья вершины $v$ , то

s u m [v] = 1 + s u m [t o_{1}] + s u m [t o_{2}] + ... + s u m [t o_{k}]

Если вершина $v$ является листом дерева, то установим $s u m [v] = 1$ .

Пример

Рассмотрим пример. Возле каждого сотрудника (вершины графа) указано количество его подчиненных.

Дерево храним в списке смежности $g$ .

vector<vector<int> > g;

Функция dfs выполняет поиск в глубину из вершины $v$ и возвращает количество вершин в поддереве с корнем $v$ . Вершина $p$ является предком $v$ при поиске в глубину.

int dfs(int v, int p)
{

Поддерево с корнем $v$ изначально содержит только одну вершину — вершину $v$ .

  sum[v] = 1;

Рассматриваем ребро $v \to t o$ . Если $t o \neq = p$ , то добавляем к $s u m [v]$ количество вершин в поддереве с корнем $t o$ .

  for (int to : g[v])
    if (to != p) sum[v] += dfs(to, v);

Возвращаем количество вершин в поддереве с корнем $v$ .

  return sum[v];
}

Основная часть программы. Читаем входные данные. Строим дерево.

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

for (i = 2; i <= n; i++)
{
  scanf("%d", &x);

Для сотрудника $i$ непосредственным начальником в компании является $x$ .

  g[i].push_back(x);
  g[x].push_back(i);
}

Запускаем поиск в глубину из вершины $1$ .

sum.resize(n + 1);
dfs(1, -1);

Выводим ответ. Количество подчиненных сотрудника $i$ равно $s u m [i] -1$ .

for (i = 1; i <= n; i++)
  printf("%d ", sum[i] - 1);
printf("\n");

Java реализация


import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g;	
  static int sum[];
  static int n;
  
  static int dfs(int v, int p)
  {
    sum[v] = 1;
    for(int to : g[v])
      if (to != p) sum[v] += dfs(to,v);
    return sum[v];
  }
  
  @SuppressWarnings("unchecked")
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    g = new ArrayList[n+1]; // unchecked
    sum = new int[n+1];

    for (int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();

    for (int i = 2; i <= n; i++)
    {
      int x = con.nextInt();
      g[i].add(x);
      g[x].add(i);
    }
    
    dfs(1,-1);
    for (int i = 1; i <= n; i++)
      System.out.print(sum[i] - 1 + " ");    
    System.out.println();
    con.close();
  }
}

Python реализация

Увеличим стек для рекурсии.

import sys
sys.setrecursionlimit(1000000)

def dfs(v, p):

Поддерево с корнем $v$ изначально содержит только одну вершину — вершину $v$ .

  sum[v] = 1

Рассматриваем ребро $v \to t o$ . Если $t o \neq = p$ , то добавляем к $s u m [v]$ количество вершин в поддереве с корнем $t o$ .

  for to in g[v]:
    if to != p: sum[v] += dfs(to,v)

Возвращаем количество вершин в поддереве с корнем $v$ .

  return sum[v]

Основная часть программы. Читаем количество сотрудников $n$ .

n = int(input())

Инициализируем список смежности графа $g$ .

g = [[] for _ in range(n+1)]

Читаем входные данные. Строим дерево.

lst = list(map(int, input().split()))
for i in range(2,n+1):
  a = lst[i-2]

Для сотрудника $i (i \geq 2)$ непосредственным начальником в компании является $a$ .

  g[a].append(i)
  g[i].append(a)

Инициализируем список $s u m$ .

sum = [0] * (n + 1)

Запускаем поиск в глубину из вершины $1$ .

dfs(1,-1)

Выводим ответ. Количество подчиненных сотрудника $i$ равно $s u m [i] - 1$ .

for i in range(1, n+1):
  print(sum[i] - 1,end=" ")

Дано дерево, состоящее из $n$ вершин.

Диаметр дерева — это максимальное расстояние между двумя вершинами. Найдите диаметр заданного дерева.

Вход. Первая строка содержит целое число $n (1 \leq n \leq 2 \cdot 1 0^{5})$ — количество вершин в дереве. Вершины пронумерованы числами от $1$ до $n$ .

Каждая из следующих $n - 1$ строк описывает ребро и содержит два целых числа $a$ и $b (1 \leq a, b \leq n)$ , обозначающих, что вершины $a$ и $b$ соединены ребром.

Выход. Выведите одно целое число — диаметр дерева.

Открыть задачу

Выполним поиск в глубину, начиная с любой вершины, например, с вершины $1$ . Найдём вершину, наиболее удалённую от $1$ , и обозначим её как вершину $a$ . Затем запустим поиск в глубину из вершины $a$ и найдём вершину, которая будет наиболее удалённой от $a$ . Обозначим её как вершину $b$ . Тогда расстояние между вершинами $a$ и $b$ будет максимальным и равно диаметру дерева.

Пример

Рассмотрим дерево из примера.

Диаметр дерева равен $3$ . Наибольшее расстояние достигается, например, для вершин $2$ и $5$ .

Упражнение

Найдите диаметр дерева.

Входное дерево храним в списке смежности $g$ . Кратчайшие расстояния от источника до вершин сохраняем в массиве $d i s t$ .

vector<vector<int>> g;
vector<int> dist;

Функция dfs выполняет поиск в глубину из вершины $v$ . Кратчайшее расстояние от источника до вершины $v$ равно $d$ . Предком вершины $v$ при поиске в глубину является $p$ .

void dfs(int v, int d, int p = -1)
{

Сохраняем в $d i s t [v]$ кратчайшее расстояние от источника до вершины $v$ .

  dist[v] = d;

Перебираем все ребра $(v, t o)$ . Для каждого сына $t o$ вершины $v$ (где $t o$ не является предком $v$ ) запускаем поиск в глубину. Расстояние от источника до вершины $t o$ будет равно $d + 1$ .

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

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

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

Строим неориентированное дерево.

for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

Ищем кратчайшие расстояния от вершины $1$ до всех остальных вершин. Самой удаленной от нее вершиной является $a$ .

dfs(1, 0, -1);
a = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

Ищем кратчайшие расстояния от вершины $a$ до всех остальных вершин. Самой удаленной от нее вершиной является $b$ .

dfs(a, 0,  -1);
b = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

Выводим диаметр дерева — кратчайшее расстояние от $a$ до $b$ .

printf("%d\n", dist[b]);

Задано дерево, состоящее из $n$ вершин.

Для каждой вершины определите максимальное расстояние до любой другой вершины.

Вход. Первая строка содержит целое число $n (1 \leq n \leq 2 \cdot 1 0^{5})$ — количество вершин в дереве. Вершины пронумерованы от $1$ до $n$ .

Следующие $n - 1$ строк содержат описание рёбер: каждая строка состоит из двух целых чисел $a$ и $b (1 \leq a, b \leq n)$ , обозначающих, что между вершинами $a$ и $b$ существует ребро.

Выход. Выведите $n$ целых чисел — для каждой вершины от $1$ до $n$ максимальное расстояние до любой другой вершины в дереве.

Открыть задачу

С помощью двух запусков поиска в глубину найдём диаметр дерева.

Поскольку дерево — это связный граф без циклов, как поиск в глубину (DFS), так и поиск в ширину (BFS) корректно находят кратчайшие расстояния от стартовой вершины до всех остальных.

Обозначим через $a$ и $b$ две вершины, находящиеся на максимальном расстоянии друг от друга — то есть образующие диаметр дерева.

Вычислим кратчайшие расстояния от вершины $a$ до всех остальных и сохраним их в массиве $d i s t a$ , а от вершины $b$ — в массиве $d i s t b$ .

Тогда для каждой вершины i наибольшее расстояние до другой вершины будет равно

ma x (d i s t a [i], d i s t b [i])

Пример

Рассмотрим дерево из примера.

Диаметром дерева может быть, например, путь между вершинами $2$ и $5$ .

Входное дерево хранится в виде списка смежности $g$ .

Кратчайшие расстояния от вершин $a$ и $b$ сохраняются в массивах $d i s t a$ и $d i s t b$ .

vector<vector<int>> g;
vector<int> dista, distb;

Функция dfs выполняет поиск в глубину из вершины $v$ .

Параметр $d$ обозначает кратчайшее расстояние от источника до вершины $v$ .
Результаты сохраняются в массиве $d i s t$ .
Параметр $p$ указывает на предка вершины $v$ в процессе обхода.

void dfs(int v, int d, vector<int>& dist, int p = -1)
{

Заносим в $d i s t [v]$ кратчайшее расстояние от источника до вершины $v$ .

  dist[v] = d;

Перебираем все ребра $(v, t o)$ . Для каждого сына $t o$ вершины $v$ (вершина $t o$ не является предком вершины $v$ ) запускаем поиск в глубину.

  for (int to : g[v])
    if (to != p) dfs(to, d + 1, dist, v);
}

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

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

Строим неориентированное дерево.

for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

Находим кратчайшие расстояния от вершины $1$ . Самой удалённой от неё вершиной является вершина $a$ .

dfs(1, 0, dista, -1);
a = max_element(dista.begin() + 1, dista.begin() + n + 1) - dista.begin();

Затем вычисляем кратчайшие расстояния от вершины $a$ и сохраняем их в массиве $d i s t a$ . Самой удалённой вершиной от $a$ оказывается вершина $b$ . Расстояние между вершинами $a$ и $b$ является диаметром дерева.

dfs(a, 0, dista, -1);
b = max_element(dista.begin() + 1, dista.begin() + n + 1) - dista.begin();

Вычисляем кратчайшие расстояния от вершины $b$ и сохраняем их в массиве $d i s t b$ .

dfs(b, 0, distb, -1);

Для каждой вершины $i$ выводим расстояние до самой удалённой от неё вершины.

for (i = 1; i <= n; i++)
  printf("%d ", max(dista[i], distb[i]));
printf("\n");

Python реализация

Увеличим стек для рекурсии.

import sys
sys.setrecursionlimit(1000000)

Функция dfs выполняет поиск в глубину из вершины $v$ .

Параметр $d$ обозначает кратчайшее расстояние от источника до вершины $v$ .
Результаты сохраняются в массиве $d i s t$ .
Параметр $p$ указывает на предка вершины $v$ в процессе обхода.

def dfs(v, d, dist, p =- 1):

Заносим в $d i s t [v]$ кратчайшее расстояние от источника до вершины $v$ .

  dist[v] = d

  for to in g[v]:
    if to != p:
      dfs(to, d + 1, dist, v)

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

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

Строим неориентированное дерево.

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

Находим кратчайшие расстояния от вершины $1$ . Самой удалённой от неё вершиной является вершина $a$ .

dfs(1, 0, dista)
a = dista.index(max(dista[1:]))

dfs(a, 0, dista)
b = dista.index(max(dista[1:]))

Вычисляем кратчайшие расстояния от вершины $b$ и сохраняем их в массиве $d i s t b$ .

dfs(b, 0, distb)

Для каждой вершины $i$ выводим расстояние до самой удалённой от неё вершины.

result = [max(dista[i], distb[i]) for i in range(1, n + 1)]
print(*result)

Родители подарили Роману неориентированный связный взвешенный граф с $n$ вершинами и $n - 1$ ребрами. Роман хочет найти суммарную длину всех путей между парами вершин в графе. Длиной пути считается сумма весов всех рёбер, входящих в него. Поскольку путь из вершины $u$ в вершину $v$ совпадает с путём из $v$ в $u$ , Роман считает их одним и тем же и не различает.

Вход. Первая строка содержит количество вершин в графе $n (2 \leq n \leq 1 0^{5})$ . Следующие $n - 1$ строк описывают ребра. Каждая строка содержит три целых числа: номера вершин, соединенных ребром (вершины пронумерованы числами от $1$ до $n$ ), и вес ребра.

Выход. Выведите сумму длин всех различных путей между парами вершин, вычисленную по модулю $1 0^{9}$ .

Открыть задачу

Запустим поиск в глубину из произвольной вершины дерева. Рассмотрим ребро $(u, v)$ с весом $w$ . Пусть количество вершин в поддереве с корнем $v$ равно $с$ . Тогда с одной стороны ребра находится $c$ вершин, а с другой $n - c$ вершин. Ребро $(u, v)$ входит в $c \cdot (n - c)$ различных путей между парами вершин. Следовательно, вклад ребра $(u, v)$ в суммарную длину всех путей равен $c \cdot (n - c) \cdot w$ . Остается перебрать все ребра с помощью поиска в глубину и просуммировать их вклад в общую сумму длин путей.

Пример

Графы, приведенные в примерах, имеют вид:

Рассмотрим вклад ребер в общую сумму длин всех путей в первом примере.

Ребро $(1, 2)$ весом $1$ принадлежит двум путям:

$1 - 2$ ;
$2 - 1 - 3$ ;

Его вклад в общую сумму равен $1 \cdot 2 \cdot 1 = 2$ .

Ребро $(1, 3)$ весом $3$ принадлежит двум путям:

$1 - 3$ ;
$2 - 1 - 3$ ;

Его вклад в общую сумму равен $2 \cdot 1 \cdot 3 = 6$ .

Суммарная длина всех путей равна $2 + 6 = 8$ .

Во втором примере рассмотрим вклад ребра $(1, 2)$ весом $5$ в общую сумму длин всех путей.

Количество вершин в поддереве с корнем в вершине $2$ равно $с = 4$ (включая саму вершину $2$ ). Тогда с другой стороны ребра $(1, 2)$ находится $n - c = 6 - 4 = 2$ вершины. Следовательно, количество различных путей, проходящих через ребро $(1, 2)$ , равно $c * (n - c) = 4 * 2 = 8$ . Действительно, такими путями являются все пары вершин, в которых одна вершина лежит в поддереве вершины $2$ , а другая — вне его:

1 - 2, 1 - 2 - 4, 1 - 2 - 5, 1 - 2 - 6, 3 - 1 - 2, 3 - 1 - 2 - 4, 3 - 1 - 2 - 5, 3 - 1 - 2 - 6

Вклад ребра $(1, 2)$ весом $5$ в сумму длин всех путей составляет

c \cdot (n - c) \cdot w = 4 \cdot 2 \cdot 5 = 40

Объявим значение модуля $MO D$ .

#define MOD 1000000000

Входной взвешенный граф храним в списке смежности $g$ .

vector<vector<pair<int,int> > > g;

Функция dfs реализует поиск в глубину из вершины $v$ возвращает количество вершин в поддереве с корнем $v$ (включая саму вершину $v$ ). Подсчет этих вершин ведётся в переменной $c n t$ . Изначально полагаем $c n t = 1$ , поскольку само поддерево уже содержит вершину $v$ .

int dfs(int v, int p = -1)
{
  int cnt = 1;
  for (auto edge : g[v])
  {
    int to = edge.first;
    int w = edge.second;

Рассмотрим ребро $(v, t o)$ с весом $w$ . Вычисляем количество вершин $c$ в поддереве с корнем в вершине $t o$ . Тогда с одной стороны ребра находятся $c$ вершин, а с другой $n - c$ вершин. Ребро $(v, t o)$ входит в $c \cdot (n - c)$ различных путей между парами вершин.

Таким образом, вклад ребра $(v, t o)$ в суммарную длину всех путей равен

c \cdot (n - c) \cdot w

    if (to != p)
    {
      int c = dfs(to, v);
      res = (res + 1LL * c * (n - c) * w) % MOD;
      cnt += c;
    }
  }
  return cnt;
}

Основная часть программы. Читаем входной взвешенный граф в список смежности $g$ .

scanf("%d", &n);
g.resize(n + 1);
for (i = 1; i < n; i++)
{
  scanf("%d %d %d", &u, &v, &d);
  g[u].push_back({v, d});
  g[v].push_back({u, d});
}

Запускаем поиск в глубину из вершины $1$ . Вершины графа нумеруются от $1$ до $n$ .

dfs(1);

Выводим ответ.

printf("%lld\n",res);

Java реализация

import java.util.*;
import java.io.*;

class Edge 
{
  int to;
  int weight;
  public Edge(int to, int weight) 
  {
    this.to = to;
    this.weight = weight;
  }
}

public class Main
{
  static int MOD = 1000000000;
  static ArrayList<Edge>[] g;	
  static int n, m;
  static long res;
  
  static int dfs(int v, int p)
  {
    int cnt = 1;
    for(Edge edge : g[v])
    {
      int to = edge.to;
      int w = edge.weight;
      if (to != p)
      {
        int c = dfs(to, v);
        res = (res + 1L * c * (n - c) * w) % MOD;
        cnt += c;
      }
    }
    return cnt;
  }
  
  public static void main(String[] args)
  {
    FastScanner con = new FastScanner(System.in);
    n = con.nextInt();
    g = new ArrayList[n+1]; // unchecked

    for (int i = 0; i <= n; i++)
      g[i] = new ArrayList<Edge>();

    for (int i = 1; i < n; i++)
    {
      int u = con.nextInt();
      int v = con.nextInt();
      int d = con.nextInt();
      g[u].add(new Edge(v,d));
      g[v].add(new Edge(u,d));
    }
    
    dfs(1,-1);
    System.out.println(res);    
  }
}   

class FastScanner 
{
  BufferedReader br;
  StringTokenizer st;

  public FastScanner(InputStream inputStream) 
  {
    br = new BufferedReader(new InputStreamReader(inputStream));
    st = new StringTokenizer("");
  }

  public String next() 
  {
    while (!st.hasMoreTokens()) 
    {
      try 
      {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e) 
      {
        return null;
      }
    }
    return st.nextToken();
  }
 
  public int nextInt() 
  {
    return Integer.parseInt(next());
  }
}

Python реализация

Объявим значение модуля $MO D$ .

MOD = 1000000000

def dfs(v, p = -1):
  global res
  cnt = 1
  for to, w in g[v]:

Таким образом, вклад ребра $(v, t o)$ в суммарную длину всех путей равен

c \cdot (n - c) \cdot w

    if to != p:
      c = dfs(to, v)
      res = (res + c * (n - c) * w) % MOD
      cnt += c
  return cnt

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

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

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

Запускаем поиск в глубину из вершины $1$ . Вершины графа нумеруются от $1$ до $n$ .

dfs(1)

Выводим ответ.

print(res)

Задано подвешенное дерево, состоящее из $n$ вершин. Каждая вершина окрашена в один из $n$ цветов. Для каждой вершины $v$ требуется определить количество различных цветов, встречающихся в поддереве с корнем в $v$ .

Вход. В первой строке задано число $n (1 \leq n \leq 1 0^{6})$ . Далее следуют $n$ строк, каждая из которых описывает одну вершину. В $i$ -й строке указаны два числа $p_{i} c_{i}$ , где $p_{i}$ — номер родителя вершины $i$ , а $c_{i}$ — цвет вершины $i (1 \leq c_{i} \leq n)$ . Для корня дерева $p_{i} = 0$ .

Выход. Выведите $n$ чисел — по одному для каждой вершины от $1$ до $n$ . Для каждой вершины укажите количество различных цветов в поддереве с корнем в ней.

Открыть задачу

Выполним обход дерева в глубину, начиная с корня. Для каждой вершины $i$ будем хранить множество $s_{i}$ , в котором накапливаются цвета всех вершин, входящих в поддерево с корнем в $i$ .

Если $j$ — сын вершины $i$ в процессе обхода, то множество $s_{j}$ должно быть включено в $s_{i}$ .

Количество различных цветов в поддереве с корнем в вершине $i$ равно мощности (размеру) множества $s_{i}$ .

Пример

Слева для каждой вершины указан её цвет, справа — множество цветов, содержащихся в поддереве с корнем в этой вершине.

В массиве $co l or [i]$ хранится цвет вершины $i$ . Во множестве $s [i]$ будем накапливать цвета, встречающиеся в поддереве с корнем в вершине $i$ .

Ориентированное дерево представлено в виде списка смежности графа $g$ . В массиве $res [i]$ сохраняется количество различных цветов в поддеревье с корнем в вершине $i$ .

#define MAX 1000010
int color[MAX], res[MAX];
set<int> s[MAX];
vector<vector<int> > g;

Функция dfs выполняет обход дерева в глубину, начиная с вершины $v$ .

void dfs(int v)
{

Сначала в множество $s [v]$ добавляем цвет самой вершины $v$ .

  s[v].insert(color[v]);

Перебираем ребра дерева $(v, t o)$ .

  for (int to : g[v])
  {
    dfs(to);

Для каждого ребра $(v, t o)$ добавляем множество $s [t o]$ в $s [v]$ . Если размер множества $s [v]$ меньше размера множества $s [t o]$ , то меняем их местами. Далее содержимое меньшего множества $s [t o]$ добавляем во множество $s [v]$ .

    if (s[v].size() < s[to].size()) s[v].swap(s[to]);
    s[v].insert(s[to].begin(), s[to].end());

Очищаем множество $s [t o]$ — оно нам больше не пригодится.

    s[to].clear();
  }

После этого в $res [v]$ записываем количество различных цветов в поддереве, то есть размер множества $s [v]$ .

  res[v] = s[v].size();
}

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

scanf("%d",&n);
g.resize(n+1);
for(i = 1; i <= n; i++)
{
  scanf("%d %d",&p,&c);
  g[p].push_back(i);
  color[i] = c;
}

Запускаем поиск в глубину из корня дерева — вершины с номером $0$ .

dfs(0);

Выводим ответ.

for(i = 1; i <= n; i++)
  printf("%d ",res[i]);
printf("\n");

После напряжённой рабочей недели жители Манчестера и Ливерпуля решили отправиться в поход на выходные. Прогуливаясь по лесу, они наткнулись на уникальное дерево, состоящее из $n$ вершин. Вершины дерева пронумерованы от $1$ до $n$ , и каждая из них окрашена в один из $c$ возможных цветов.

Чтобы побороть скуку, они решили проверить свои логические способности. Корнем дерева является вершина $1$ . Для каждой вершины участники решили найти ближайшего предка, цвет которого совпадает с цветом этой вершины.

Вход. Первая строка содержит два целых числа $n$ и $c (1 \leq n, c \leq 1 0^{5})$ — количество вершин в дереве и количество возможных цветов.

Вторая строка содержит $n - 1$ целых чисел: $i$ -ое из них указывает на родителя вершины $i + 1$ .

Третья строка содержит $n$ целых чисел — цвета вершин. Каждый цвет лежит в диапазоне от $1$ до $c$ включительно.

Выход. Выведите в одной строке $n$ чисел: для каждой вершины выведите номер её ближайшего предка с таким же цветом. Если такого предка не существует, выведите $- 1$ .

Открыть задачу

Рассмотрим упрощённый вариант задачи. Пусть все вершины дерева окрашены в один цвет. Объявим стек, который изначально пуст. Запустим обход в глубину из корня дерева. При входе в вершину $v$ добавим её в стек, а при завершении обработки вершины $v$ удалим верхний элемент стека (им как раз и будет вершина $v$ ). После завершения обхода стек вновь станет пустым.

Вопрос: что будет находиться на вершине стека в момент входа в вершину $v$ , до того как мы поместим $v$ в стек?

Теперь перейдём к решению исходной задачи. Создадим $c$ стеков — по одному для каждого цвета (например, можно использовать вектор стеков). Изначально все стеки пусты. Запустим обход в глубину из корня дерева — вершины $1$ . Обработка вершины $v$ , окрашенной в цвет $co l or$ , включает следующие шаги:

Если стек $s [co l or]$ не пуст, то на его вершине находится номер вершины, которая является ближайшим предком вершины $v$ того же цвета. Если стек пуст, то такой вершины не существует, и в качестве ответа для вершины $v$ следует вывести $- 1$ .
Добавляем вершину $v$ в стек $s [co l or]$ .
Рекурсивно запускаем поиск в глубину от всех сыновей вершины $v$ .
После завершения обработки удаляем вершину $v$ из стека $s [co l or]$ .

Во время обхода в глубину, находясь в вершине $v$ , в стеках содержится информация о цветах всех вершин, расположенных на единственном пути от корня дерева до вершины $v$ . В частности, стек $s [co l or]$ хранит номера вершин на этом пути, окрашенных в цвет $co l or$ . Эти вершины заносятся в стек в порядке их посещения при обходе в глубину.

Пример

Когда поиск в глубину дойдет до вершины $5$ , из $c = 4$ стеков два будут пустыми (соответствующие цветам $3$ и $4$ ).

Стек номер $1$ (для цвета $1$ ) будет содержать вершину $1$ , стек номер $2$ (для цвета $2$ ) будет содержать вершину $3$ . Так как вершина $5$ имеет цвет $2$ , её ближайший предок с таким же цветом находится на вершине стека номер $2$ .

Таким образом, ближайшим предком вершины $5$ по цвету является вершина $3$ .

Объявим рабочие массивы.

vector<int> col, res;
vector<vector<int> > g;
vector<stack<int> > s;

Функция dfs выполняет поиск в глубину, начиная с вершины $v$ .

void dfs(int v)
{

Вершина $v$ имеет цвет $co l or$ .

  int color = col[v];

Номер ближайшего предка вершины $v$ , имеющей цвет $co l or$ , сохраняем в $res [v]$ .

  if(s[color].empty())
    res[v] = -1;
  else
    res[v] = s[color].top();

Заносим вершину $v$ в стек номер $co l or$ .

  s[color].push(v);

Перебираем всех сыновей $t o$ вершины $v$ и рекурсивно запускаем из них поиск в глубину.

  for (int to : g[v])
    dfs(to);

После завершения обработки вершины $v$ (то есть при выходе) удаляем её из стека с номером $co l or$ .

  s[color].pop();
}

Основная часть программы. Читаем входные данные. Строим дерево.

scanf("%d %d", &n, &c);
g.resize(n + 1);
for(i = 2; i <= n; i++)
{
  scanf("%d",&val);
  g[val].push_back(i);
}

Читаем цвета вершин дерева.

col.resize(n + 1);
for(i = 1; i <= n; i++)
  scanf("%d",&col[i]);

Запускаем поиск в глубину из вершины $1$ .

s.resize(c + 1);
res.resize(n + 1);
dfs(1);

Выводим ответ.

for(i = 1; i <= n; i++)
  printf("%d ",res[i]);
printf("\n");

Python реализация

Увеличим стек для рекурсии.

import sys
sys.setrecursionlimit(1000000)

Функция dfs выполняет поиск в глубину, начиная с вершины $v$ .

def dfs(v):

Вершина $v$ имеет цвет $co l or$ .

  color = col[v]

Номер ближайшего предка вершины $v$ , имеющей цвет $co l or$ , сохраняем в $res [v]$ .

  if not s[color]:
    res[v] = -1
  else:
    res[v] = s[color][-1]

Заносим вершину $v$ в стек номер $co l or$ .

  s[color].append(v)

Перебираем всех сыновей $t o$ вершины $v$ и рекурсивно запускаем из них поиск в глубину.

  for to in g[v]:
    dfs(to)

После завершения обработки вершины $v$ (то есть при выходе) удаляем её из стека с номером $co l or$ .

  s[color].pop()

Основная часть программы. Читаем входные данные. Строим дерево.

n, c = map(int, input().split())
lst = list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
  val = lst[i - 2]
  g[val].append(i)

Читаем цвета вершин дерева.

col = [0] * (n + 1)
col[1:] = list(map(int, input().split()))

Запускаем поиск в глубину из вершины $1$ .

s = [[] for _ in range(c + 1)]
res = [0] * (n + 1)
dfs(1)

Выводим ответ.

print(*res[1:])

В свободное время фермер Джон создал собственную видеоплатформу под названием MooTube. На MooTube его коровы могут записывать, публиковать и находить множество забавных видеороликов. К настоящему моменту коровы разместили $n$ видео с номерами от $1$ до $n$ .

Однако фермер Джон не до конца понимает, как помочь своим коровам находить новые видео, которые им могут понравиться. Он хочет реализовать для каждого видео систему рекомендаций – список "рекомендуемых видео", основанный на их схожести с уже просмотренными роликами.

Чтобы определить, насколько два видео похожи друг на друга, Джон вводит метрику релевантности. Он вручную оценивает $n - 1$ пар видео и присваивает каждой паре значение релевантности. На основе этих пар Джон строит сеть, где каждое видео представляет собой вершину графа, а отобранные им пары соединяются рёбрами с указанной релевантностью.

Для удобства Джон выбирает такие $n - 1$ пары, чтобы между любыми двумя видео существовал единственный путь — то есть видеосеть представляет собой дерево.

Он решает, что релевантность между двумя видео должна определяться как минимальная релевантность среди всех рёбер на пути между ними.

Теперь фермер Джон хочет выбрать значение $k$ таким образом, чтобы для каждого видео на MooTube отображались все другие видео, релевантность которых к нему составляет не менее $k$ . Однако он опасается, что слишком большое количество рекомендаций может отвлечь коров от производства молока, поэтому ему важно точно оценить, сколько видео будет рекомендовано для разных значений $k$ .

Фермер Джон обращается к Вам за помощью: нужно ответить на несколько запросов, каждый из которых содержит значение $k$ и номер видео. Для каждого запроса требуется определить, сколько других видео будет рекомендовано для просмотра, если минимальная допустимая релевантность составляет $k$ .

Вход. Первая строка содержит два целых числа $n$ и $q (1 \leq n, q \leq 5000)$ — количество видеороликов и количество запросов соответственно.

Следующие $n - 1$ строк описывают пары видеороликов, релевантность между которыми фермер Джон оценивает вручную. Каждая строка содержит три целых числа $p_{i}, q_{i}$ и $r_{i} (1 \leq p_{i}, q_{i} \leq n, 1 \leq r_{i} \leq 1 0^{9})$ , что означает, что видеоролики с номерами $p_{i}$ и $q_{i}$ связаны ребром с релевантностью $r_{i}$ .

Далее следуют $q$ строк, каждая из которых описывает один запрос от фермера Джона. В $i$ -й строке содержатся два целых числа $k_{i}$ и $v_{i} (1 \leq k_{i} \leq 1 0^{9}, 1 \leq v_{i} \leq n)$ — это означает что в $i$ -ом запросе ФД интересуется, сколько видеороликов будет рекомендовано для видео с номером $v_{i}$ , если минимально допустимая релевантность рекомендаций равна $k = k_{i}$ .

Выход. Выведите $q$ строк. В $i$ - ой строке выведите ответ на $i$ - ый вопрос ФД.

Пример. Фермер Джон установил следующие связи между видео:

Видео $1$ и $2$ имеют релевантность $3$ ,
Видео $2$ и $3$ — релевантность $2$ ,
Видео $2$ и $4$ — релевантность $4$ .

На основании этих данных можно вычислить релевантность между другими парами видео:

Видео $1$ и $3$ : релевантность = $min (3, 2) = 2$ ,
Видео $1$ и $4$ : релевантность = $min (3, 4) = 3$ ,
Видео $3$ и $4$ : релевантность = $min (2, 4) = 2$ .

Теперь рассмотрим, какие видео будут рекомендованы при следующих запросах:

Из видео $2$ при $k = 1$ будут рекомендованы видео $1, 3$ и $4$ .
Из видео $1$ при $k = 3$ будут рекомендованы видео $2$ и $4$ .
Из видео $1$ при $k = 4$ не будет рекомендовано ни одно видео.

Открыть задачу

Для каждого запроса, заданного парой $(k_{i}, v_{i})$ запустим поиск в глубину или в ширину, начиная с вершины $v_{i}$ . При этом двигаться по графу будем только по рёбрам, релевантность которых не меньше значения $k_{i}$ . Подсчитаем количество достигнутых вершин $res$ , не считая начальную вершину $v_{i}$ . Значение $res$ и будет ответом на запрос $(k_{i}, v_{i})$ .

Пример

Фермер Джон установил следующие связи между видео:

Видео $1$ и $2$ имеют релевантность $3$ ,
Видео $2$ и $3$ — релевантность $2$ ,
Видео $2$ и $4$ — релевантность $4$ .

На основании этих данных можно вычислить релевантность между другими парами видео:

Видео $1$ и $3$ : релевантность = $min (3, 2) = 2$ ,
Видео $1$ и $4$ : релевантность = $min (3, 4) = 3$ ,
Видео $3$ и $4$ : релевантность = $min (2, 4) = 2$ .

Теперь рассмотрим, какие видео будут рекомендованы при следующих запросах:

Из видео $2$ при $k = 1$ будут рекомендованы видео $1, 3$ и $4$ .
Из видео $1$ при $k = 3$ будут рекомендованы видео $2$ и $4$ .
Из видео $1$ при $k = 4$ не будет рекомендовано ни одно видео.

Входной граф храним в списке смежности $g$ .

vector<vector<pair<int, int>>> g;

Функция bfs реализует поиск в ширину из вершины $s t a r t$ и возвращает количество посещенных вершин, не включая саму начальную вершину $s t a r t$ . В процессе поиска мы переходим только по тем ребрам, вес которых не меньше заданного значения $k$ .

int bfs(int start, int k)
{

Массив кратчайших расстояний в данной задаче не требуется — достаточно лишь отслеживать, была ли вершина посещена. Если вершина $i$ была посещена, устанавливаем $u se d [i] = 1$ .

  vector<int> used(n + 1);
  used[start] = 1;

Инициализируем очередь и добавляем в неё стартовую вершину $s t a r t$ .

  queue<int> q;
  q.push(start);

Количество посещенных вершин при поиске в ширину (не считая начальную вершину $s t a r t$ ) подсчитываем в переменной $res$ .

  int res = 0;

Запускаем поиск в ширину.

  while (!q.empty())
  {

Извлекаем вершину $v$ из очереди $q$ .

    int v = q.front(); q.pop();

Перебираем ребра, смежные с вершиной $v$ .

    for (auto edge : g[v])
    {

Рассматриваем ребро $(v, t o)$ весом $k t o$ .

     int to = edge.first;
     int kto = edge.second;

Если вес ребра $k t o$ меньше $k$ , то такое ребро не рассматриваем (переход по нему запрещён).

      if (kto < k) continue;

Если вершина $t o$ еще не была посещена, то добавляем ее в очередь, отмечаем как посещённую и увеличиваем счётчик посещённых вершин $res$ на $1$ .

      if (used[to] == 0)
      {
        q.push(to);
        used[to] = 1;
        res++;
      }
    }
  }

Возвращаем ответ на запрос.

  return res;
}

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

scanf("%d %d", &n, &qu);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &p, &q, &r);

Добавляем в список смежности неориентированное ребро $(p, q)$ весом $r$ .

  g[p].push_back({ q, r });
  g[q].push_back({ p, r });
}

Последовательно обрабатываем $q u$ запросов.

while (qu--)
{
  scanf("%d %d", &k, &v);

Запускаем поиск в ширину из вершины $v$ . Выводим количество вершин, посещенных в результате поиска в ширину.

  printf("%d\n", bfs(v, k));
}

Реализация алгоритма – поиск в глубину

Входной граф храним в списке смежности $g$ .

vector<vector<pair<int, int>>> g;

Функция dfs выполняет поиск в глубину, начиная с вершины $v$ , и возвращает количество посещенных вершин. В процессе поиска мы перемещаемся только по тем ребрам, у которых вес не меньше заданного значения $k$ .

int dfs(int v, int k)
{

Отмечаем вершину $v$ как посещённую.

  used[v] = 1;

В переменной $res$ подсчитываем количество вершин, посещённых в поддереве с корнем в $v$ в ходе выполнения поиска в глубину.

  int res = 1;

Перебираем ребра, смежные с вершиной $v$ .

  for (auto edge : g[v])
  {

Рассматриваем ребро $(v, t o)$ весом $k t o$ .

    int to = edge.first;
    int kto = edge.second;

Если вес ребра $k t o$ меньше $k$ , то такое ребро не рассматриваем (переход по нему запрещён).

    if (kto < k) continue;

Если вершина $t o$ еще не была посещена, то запускаем из нее поиск в глубину. Количество посещенных вершин в поддереве с корнем $t o$ прибавляем к $res$ .

    if (used[to] == 0)
      res += dfs(to, k);
  }
  return res;
}

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

scanf("%d %d", &n, &qu);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &p, &q, &r);

Добавляем в список смежности неориентированное ребро $(p, q)$ весом $r$ .

  g[p].push_back({ q, r });
  g[q].push_back({ p, r });
}

Последовательно обрабатываем $q u$ запросов.

while (qu--)
{
  scanf("%d %d", &k, &v);

Запускаем поиск в глубину из вершины $v$ . Выводим количество вершин, посещенных в результате поиска в глубину, не считая саму вершину $v$ .

  used.assign(n + 1, 0);
  printf("%d\n", dfs(v, k) - 1);
}

Задано дерево с $n$ вершинами. Ребра дерева имеют вес только $0$ или $1$ . Найдем XOR сумму между всеми парами вершин. Вычислите сумму всех XOR сумм.

Выход. Выведите сумму XOR сумм между всеми парами вершин.

Открыть задачу

При помощи поиска в глубину вычислим XOR сумму между вершиной $1$ и всеми остальными вершинами. XOR сумму между вершинами $1$ и $v$ занесем в $x [v]$ . Пусть $o n es$ — количество единиц, а $zeroes$ — количество нулей в массиве $x (o n es + zeroes = n)$ . Тогда ответом на задачу будет число $o n es \cdot zeroes$ .

Пример

Рассмотрим граф, приведенный в примере.

Возле каждой вершины $v$ записана XOR сумма $x [v]$ между $1$ и $v$ . Если $x [v] = x [u]$ для некоторых вершин $v$ и $u$ , то XOR сумма между ними равна $0$ , таким образом совершая вклад $0$ в общую сумму. XOR сумма для каждой пары вершин $(v, u)$ , для которой $x [v] \neq = x [u]$ , дает вклад $1$ в общую сумму.

Следовательно ответ равен количеству пар вершин $(v, u)$ , для которых $x [v] \neq = x [u]$ . Это число равно $o n es \cdot zeroes = 2 \cdot 3 = 6$ . Парами вершин, дающими $1$ в общую сумму, будут: $(1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5)$ .

Входной граф храним в списке смежности $g$ . Объявим массив $x$ .

vector<vector<pair<int,int> > > g;
vector<int> x;

Функция dfs реализует поиск в глубину, который вычисляет XOR сумму $x [v]$ между вершинами $1$ и $v$ . Текущая XOR сумма между $1$ и $v$ равна $c u r_x or$ . Предком вершины $v$ является $p$ .

void dfs(int v, int cur_xor, int p = -1)
{
  x[v] = cur_xor;
  for (auto z : g[v])
  {
    int to = z.first;
    int w = z.second;
    if (to != p) dfs(to, cur_xor ^ w, v);
  }
}

Основная часть программы. Читаем входной граф.

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

for (i = 1; i < n; i++)
{
  scanf("%d %d %d", &u, &v, &d);
  g[u].push_back({v, d});
  g[v].push_back({u, d});
}

Запускаем поиск в глубину из вершины $1$ .

dfs(1, 0, -1);

Вычисляем количество нулей $zeroes$ и единиц $o n es$ в массиве $x$ .

ones = 0;
for (i = 1; i <= n; i++)
  if (x[i] == 1) ones++;
zeroes = n - ones;

Выводим ответ.

printf("%lld\n", 1LL * ones * zeroes);

Python реализация

def dfs(v, cur_xor = 0, p = -1):
  x[v] = cur_xor
  for to, w in g[v]:
    if to != p:
      dfs(to, cur_xor ^ w, v)

Основная часть программы. Читаем входной граф.

n = int(input())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
  u, v, d = map(int, input().split())
  g[u].append((v, d))
  g[v].append((u, d))

Инициализируем массив $x$ .

x = [0] * (n + 1)

Запускаем поиск в глубину из вершины $1$ .

dfs(1)

Вычисляем количество нулей $zeroes$ и единиц $o n es$ в массиве $x$ .

ones = sum(x)
zeroes = n - ones

Выводим ответ.

print(ones * zeroes)

Дано дерево с $n$ вершинами, пронумерованными от $1$ до $n$ . $i$ - ое ребро дерева соединяет вершины $a_{i}$ и $b_{i}$ . Вершина $i$ окрашена в цвет $c_{i}$ (в этой задаче цвета представлены целыми числами).

Вершина $x$ считается хорошей, если кратчайший путь от вершины $1$ до вершины $x$ не содержит ни одной вершины, окрашенной в тот же цвет, что и вершина $x$ , за исключением самой вершины $x$ .

Найдите все хорошие вершины.

Вход. Первая строка содержит целое число $n (2 \leq n \leq 1 0^{5})$ — количество вершин.

Вторая строка содержит $n$ целых чисел — цвета вершин $c_{1}, c_{2}, ..., c_{n} (1 \leq c_{i} \leq 1 0^{5})$ .

Каждая из следующих $n - 1$ строк содержит два целых числа $a_{i}$ и $b_{i} (1 \leq a_{i}, b_{i} \leq n)$ — рёбра дерева.

Выход. Выведите все хорошие вершины по одной в строке, в порядке возрастания их номеров.

Открыть задачу

Запустим поиск в глубину из вершины $1$ . При входе в вершину $v$ цвета $co l or [v]$ увеличим значение $u se d [co l or [v]]$ на $1$ . Значение $u se d [co l or [v]]$ содержит, сколько раз цвет $co l or [v]$ встретилась на пути от вершины $1$ до вершины $v$ (включительно). Если цвет $co l or [v]$ на этом пути встретился только один раз, значит вершина $v$ является хорошей, и мы добавляем её в результирующее множество.

При выходе из вершины $v$ значение $u se d [co l or [v]]$ следует уменьшить на $1$ .

Пример

Граф из первого примера выглядит следующим образом:

Вершина $5$ не является хорошей, так как на пути $1 - 2 - 5$ вершины $5$ и $1$ имеют одинаковый цвет.

Вершина $6$ является хорошей, так как на пути $1 - 2 - 3 - 6$ цвета всех промежуточных вершин отличаются от цвета вершины $6$ .

Входной граф храним в списке смежности $g$ . Объявим рабочие массивы.

vector<int> used, color;
vector<vector<int>> g;
set<int> st;

Функция dfs реализует поиск в глубину. Переменная $p a r$ является предком вершины $v$ .

void dfs(int v, int par)
{

Вершина $v$ имеет цвет $co l or [v]$ . Отмечаем, что на пути от вершины $1$ встретилась вершина этого цвета.

  used[color[v]]++;

Значение $u se d [co l or [v]]$ показывает, сколько раз цвет $co l or [v]$ встретился на пути от вершины $1$ до вершины $v$ (включительно). Если этот цвет встретился на пути ровно один раз, то вершина $v$ считается хорошей, и мы добавляем её в результирующее множество $s t$ .

  if (used[color[v]] == 1) st.insert(v);

Перебираем все ребра $(v, t o)$ , исходящие из вершины $v$ . Если вершина $t o$ не является предком $v (t o \neq = p a r)$ , запускаем из нее поиск в глубину. При этом предком $t o$ становится $v$ .

  for (int to : g[v])
    if (to != par) dfs(to, v);

При выходе из вершины $v$ уменьшаем значение $u se d [co l or [v]]$ на $1$ .

  used[color[v]]--;
}

Основная часть программы. Читаем количество вершин $n$ и массив цветов.

scanf("%d", &n);
color.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &color[i]);

Читаем граф.

used.resize(100001);
g.resize(n + 1);
for (i = 1; i < n; i++)
{
  scanf("%d %d", &x, &y);
  g[x].push_back(y);
  g[y].push_back(x);
}

Запускаем поиск в глубину из вершины $1$ .

dfs(1, 1);

Выводим хорошие вершины. Они содержатся во множестве $s t$ .

for (int val : st)
  printf("%d\n", val);

Вам дано дерево с $n$ вершинами и $n - 1$ ребрами. Вершины пронумерованы от $1$ до $n$ , $i$ -ое ребро соединяет вершины $a_{i}$ и $b_{i}$ .

У Вас имеется $k$ цветов. Для каждой вершины в дереве Вы выбираете один из $k$ цветов для ее покраски, чтобы выполнялось следующее условие:

Если расстояние между двумя разными вершинами $x$ и $y$ меньше или равно двум, то $x$ и $y$ имеют разные цвета.

Сколько существует способов раскрасить дерево? Найдите ответ по модулю $1 0^{9} + 7$ .

Вход. Первая строка содержит два числа $n$ и $k (1 \leq n, k \leq 1 0^{5})$ . Каждая из следующих $n - 1$ строк содержит два целых числа $a_{i}$ и $b_{i} (1 \leq a_{i}, b_{i} \leq n)$ .

Выход. Выведите количество способов раскрасить дерево по модулю $1 0^{9} + 7$ .

Открыть задачу

Начнем раскраску дерева с вершины $1$ . Ее можно покрасить $k$ цветами.

Пусть мы находимся в вершине $v$ . Если она не имеет предка ( $v = 1$ ), то сыновей можно раскрасить $k - 1$ цветами. Если вершин $v$ имеет предка, то ее сыновей можно покрасить $k - 2$ цветами. Поскольку расстояние между сыновьями вершины $v$ равно $2$ , то их нельзя раскрашивать одинаковыми цветами.

Пусть для определенности вершина $v$ имеет предка. Тогда первого сына $v$ можно покрасить $k - 2$ цветами, второго сына $k - 3$ цветами и так далее.

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

Пример

Для первого примера имеется $6$ способов раскраски:

Рассмотрим второй тест. Возле каждой вершины укажем количество цветов, которыми ее можно раскрасить. Например, вершину $5$ можно раскрасить 2 цветами, так как ее цвет не должен совпадать с цветами вершин $1$ и $4$ . Общее количество способов раскрасить дерево равно $4 \cdot 3 \cdot 2 \cdot 1 \cdot 2 = 48$ .

Входной граф храним в списке смежности $g$ . Объявим константу — модуль $MO D$ .

#define MOD 1000000007
vector<vector<int>> g;

Функция dfs возвращает количество способов раскрасить дерево с корнем в вершине $v$ по модулю $MO D = 1 0^{9} + 7$ . Предком вершины $v$ является $p$ . Вершину $v$ можно покрасить $co l$ цветами.

int dfs(int v, int col, int p = -1)
{
  long long res = col;

Мы находимся в вершине $v$ . В переменной $c n t$ отмечаем количество цветов, которыми нельзя красить сыновей вершины $v$ . Изначально установим $c n t = 1$ , так как сыновья вершины $v$ не могут иметь цвет вершины $v$ . Если вершина $v$ имеет предка ( $p \neq = - 1$ ), то сыновья вершины $v$ также не могут иметь цвет предка $v$ .

  int cnt = 1;
  if (p >= 0) cnt++;

Перебираем сыновей to вершины $v$ .

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

Вершина $t o$ может быть покрашена $k - c n t$ цветами. С каждым сыном значение $c n t$ будет увеличиваться на $1$ .

      res = (res * dfs(to, k - cnt, v)) % MOD;
      cnt++;
    }
  return res;
}

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

scanf("%d %d", &n, &k);
g.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);
}

Запускаем поиск в глубину из вершины $1$ . Вершину номер $1$ можно покрасить $k$ цветами.

res = dfs(1, k);

Выводим ответ.

printf("%lld\n", res);

Python реализация

Установим максимальную глубину стека интерпретатора Python.

import sys
sys.setrecursionlimit(1000000)

Объявим константу — модуль $MO D$ .

MOD = 1000000007

def dfs(v, col, p = -1):
  res = col

  cnt = 1
  if p >= 0: cnt += 1

Перебираем сыновей $t o$ вершины $v$ .

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

Вершина $t o$ может быть покрашена $k - c n t$ цветами. С каждым сыном значение $c n t$ будет увеличиваться на $1$ .

      res = (res * dfs(to, k - cnt, v)) % MOD
      cnt += 1
  return res

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

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

Запускаем поиск в глубину из вершины $1$ . Вершину номер $1$ можно покрасить $k$ цветами.

res = dfs(1, k)

Выводим ответ.

print(res)

В стране есть $n$ городов и $n - 1$ двусторонняя дорога, причем из любого города можно добраться до любого другого, двигаясь только по дорогам. Города пронумерованы целыми числами от $1$ до $n$ включительно.

Все дороги изначально считаются плохими, однако правительство планирует улучшить состояние некоторых из них. Граждане будут довольны улучшением, если на пути от столицы, расположенной в городе $1$ , до любого другого города будет не более одной плохой дороги.

Определите количество способов улучшить качество некоторых дорог, чтобы удовлетворить это требование. Так как ответ может быть очень большим, выведите его по модулю $1 0^{9} + 7$ .

Вход. В первой строке задано одно целое число $n (2 \leq n \leq 2 \cdot 1 0^{5})$ — количество городов в стране. Во второй строке задано $n - 1$ целых положительных чисел $p_{2}, p_{3}, p_{4}, \dots, p_{n} (1 \leq p_{i} \leq i - 1)$ — описание дорог страны. Число $p_{i}$ означает, что в стране имеется дорога, соединяющая город $p_{i}$ и город $i$ .

Выход. Выведите количество способов улучшить качество дорог по модулю $1 0^{9} + 7$ .

Открыть задачу

Пусть $f (v)$ — количество способов улучшить качество дорог для поддерева с корнем в вершине $v$ . Обозначим через $t o$ сына вершины $v$ .

Если дорога $(v, t o)$ остается плохой, то все дороги в поддереве с корнем в вершине $t o$ должны быть улучшены.
Если дорогу $(v, t o)$ улучшить, то количество способов улучшить качество дорог для поддерева с корнем в вершине $t o$ равно $f (t o)$ .

Пусть $t o_{1}, t o_{2}, ..., t o_{k}$ — сыновья $v$ . Тогда

f (v) = (f (t o_{1}) + 1) \cdot (f (t o_{2}) + 1) \cdot ... \cdot (f (t o_{k}) + 1)

Если $v$ — лист (вершина, не имеющая сыновей), то положим $f (v) = 1$ .

Пример

Рассмотрим примеры, приведённые в условии. Для каждой вершины $v$ запишем значение $f (v)$ .

В первом примере существует $4$ способа улучшить качество дорог, при которых на пути от города $1$ до любого другого города имеется не более одной плохой дороги. Плохие дороги обозначены пунктирными линиями, а хорошие — сплошными.

Все вычисления выполняются по модулю $MO D = 1 0^{9} + 7$ .

#define MOD 1000000007

Функция dfs вычисляет значение $f (v)$ — количество способов улучшить качество дорог для поддерева с корнем в вершине $v$ . Предком $v$ является вершина $p$ .

long long dfs(int v, int p = -1)
{
  long long s = 1;

Если $t o_{1}, t o_{2}, ..., t o_{k}$ — сыновья $v$ , то

f (v) = (f (t o_{1}) + 1) \cdot (f (t o_{2}) + 1) \cdot ... \cdot (f (t o_{k}) + 1)

  for (int to : g[v])
    if (to != p)
    {
      long long sub = dfs(to, v);
      s = (s * (sub + 1)) % MOD;
    }
  return s;
}

Читаем входные данные. Строим дерево.

scanf("%d", &n);
g.resize(n + 1);
for (i = 2; i <= n; i++)
{
  scanf("%d", &p);
  g[i].push_back(p);
  g[p].push_back(i);
}

Вычисляем и выводим результат.

res = dfs(1);
printf("%lld\n", res);

В ясные летние дни Нюша любит ловить бабочек на свежем воздухе. Но сегодня ей попалась особенно хитрая бабочка: она залетела в лабиринт и попыталась скрыться там от Нюши.

Лабиринт состоит из $n$ комнат, пронумерованных от $1$ до $n$ , некоторые из которых соединены коридорами. Известно, что между любыми двумя комнатами существует единственный путь, проходящий только по коридорам. Иными словами, лабиринт представляет собой дерево, состоящее из $n$ вершин и $n - 1$ рёбер.

Вход в лабиринт находится в комнате с номером $1$ . Листом называется любая комната, соединённая ровно с одной другой комнатой и не совпадающая с корнем (комнатой номер $1$ ). В каждом листе расположен выход из лабиринта. Бабочка начинает свой полёт из комнаты номер $1$ в направлении одного из выходов. Она движется с постоянной скоростью, не разворачивается, и каждую минуту пролетает один коридор, переходя в соседнюю комнату. Все коридоры имеют одинаковую длину.

Чтобы поймать бабочку, Нюша решила позвать на помощь несколько друзей. Изначально каждый из них может занять любую из комнат с выходом. Как только бабочка начнёт движение от входа к какому-либо выходу, друзья могут сразу же начать двигаться из своих комнат по направлению ко входу. Они двигаются с той же скоростью, что и бабочка. Если кто-либо из них встретит бабочку — будь то в комнате или на середине коридора – она считается пойманной. Если же бабочка доберётся до выхода, не столкнувшись ни с одним из друзей, она благополучно выберется на свободу.

Помогите Нюше определить минимальное число друзей, необходимое для того, чтобы гарантированно поймать бабочку, вне зависимости от того, к какому выходу она полетит.

Вход. Первая строка содержит одно целое число $n (2 \leq n \leq 200000)$ — количество комнат в лабиринте.

Следующие $n - 1$ строк описывают коридоры, соединяющие комнаты. В каждой из них записаны два целых числа $u$ и $v (1 \leq u, v \leq n, u \neq = v)$ — номера комнат, соединённых коридором.

Гарантируется, что заданная система коридоров образует дерево.

Выход. Выведите одно целое число — минимальное количество друзей, необходимое для того, чтобы гарантированно поймать бабочку.

Открыть задачу

Выполним обход в глубину из вершины $1$ . Для каждой вершины вычислим два значения:

$d [v]$ — расстояние от вершины $1$ до вершины $v$ . Если $p$ — родитель $v$ , то
$d [v] = d [p] + 1$
$h [v]$ — расстояние от вершины $v$ до ближайшего листа в поддереве с корнем $v$ . Если $t o_{1}, t o_{2}, ..., t o_{k}$ — сыновья вершины $v$ , то
$h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])$
Если $v$ — лист дерева, то положим $h [v] = 0$ .

Затем запустим второй обход в глубину. В ходе этого обхода будем вычислять значение $res [v]$ — минимальное количество друзей, которых нужно разместить в некоторых из листьев поддерева с корнем в вершине $v$ , чтобы гарантированно поймать бабочку, при условии, что она выбрала это поддерево.

Если $h [v] \leq d [v]$ , то $res [v] = 1$ . В этом случае достаточно разместить одного друга в листе с минимальной глубиной в поддереве вершины $v$ : он успеет дойти до вершины $v$ не позже, чем бабочка — из корня дерева.

В противном случае, если $t o_{1}, t o_{2}, ..., t o_{k}$ — сыновья вершины $v$ , то

res [v] = res [t o_{1}] + res [t o_{2}] + ... + res [t o_{k}]

Если бабочка не будет поймана в самой вершине $v$ , необходимо быть готовыми перехватить её в любом из поддеревьев, исходящих из сыновей $v$ .

Искомым ответом на задачу является значение $res [1]$ .

Пример

В первом примере (на рисунке слева) требуются два друга, которых необходимо разместить у двух выходов. Бабочка может полететь из вершины $1$ либо в вершину $2$ , либо в вершину $3$ . В любом из этих случаев её перехватит один из друзей Нюши.

Во втором примере (на рисунке справа) достаточно одного друга, которого можно разместить в любом из двух выходов — вершине $3$ или $4$ . За одну минуту бабочка долетит из вершины $1$ до вершины $2$ . За это же время друг доберётся до вершины $2$ и поймает бабочку там.

Рассмотрим следующий пример. Для поимки бабочки Нюше понадобятся три друга.

Объявим константу бесконечность и рабочие массивы.

#define INF 2000000000
vector<vector<int> > g;
vector<int> d, h, res;

Функция dfs $(v, p, c n t)$ выполняет обход в глубину, начиная с вершины $v$ , и возвращает значение $h [v]$ . При этом $p$ — предок вершины $v$ , а $c n t$ — расстояние от вершины $1$ до $v$ . В процессе обхода для каждой вершины $v$ вычисляются значения $d [v]$ и $h [v]$ .

int dfs(int v, int p = -1, int cnt = 0)
{

Значение $c n t$ , равное расстоянию от вершины $1$ до $v$ , сохраняем в $d [v]$ .

  d[v] = cnt;
  int height = INF;

Перебираем всех сыновей вершины $v$ . Рассматриваем ребро $v \to t o$ . Если $t o$ совпадает с предком $v (t o = p)$ , переходим к следующему сыну.

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

В переменной $h e i g h t$ вычисляем значение

min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}]),

где $t o_{1}, t o_{2}, ..., t o_{k}$ — сыновья вершины $v$ .

h e i g h t = min (h e i g h t, df s (t o, v, c n t + 1));

Если $h e i g h t = I NF$ , значит вершина $v$ является листом, и следует установить $h [v] = 0$ . В противном случае возвращаем

h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])

  return h[v] = (height == INF) ? 0 : 1 + height;
}

Функция dfs2 $(v, p)$ выполняет обход в глубину, начиная с вершины $v$ , и возвращает значение $res [v]$ . Здесь $p$ — предок вершины $v$ .

int dfs2(int v, int p = -1)
{
  int s = 0;

Пусть $t o_{1}, t o_{2}, ..., t o_{k}$ — сыновья вершины $v$ . В переменной $s$ вычислим сумму:

res [t o_{1}] + res [t o_{2}] + ... + res [t o_{k}]

  for (int to : g[v])
    if (to != p)
    {
      dfs2(to, v);
      s += res[to];
    }

Если $h [v] \leq d [v]$ , то достаточно одного друга, и $res [v] = 1$ . Иначе

res [v] = res [t o_{1}] + res [t o_{2}] + ... + res [t o_{k}] = s

  return res[v] = (h[v] <= d[v]) ? 1 : s;
}

Основная часть программы. Читаем входные данные. Строим граф.

scanf("%d", &n);
g.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);
}

Инициализируем массивы.

d.resize(n + 1);
h.resize(n + 1);
res.resize(n + 1);

Запускаем два обхода в глубину. Первый обход для каждой вершины $v$ вычисляет значения $d [v]$ и $h [v]$ .

dfs(1);
dfs2(1);

Выводим ответ — минимальное количество друзей, необходимое для поимки бабочки.

printf("%lld\n", res[1]);

Кефа решил отпраздновать свой первый крупный заработок походом в ресторан.

Он живет рядом с необычным парком, который представляет собой подвешенное дерево из $n$ вершин c корнем в вершине $1$ . В вершине $1$ также находится дом Кефы. К сожалению для нашего героя, в парке обитают коты, и Кефа уже выяснил номера вершин, в которых они находятся.

Рестораны расположены в листовых вершинах парка. Кефа хочет выбрать ресторан, но он очень боится котов. Поэтому он ни за что не пойдёт в ресторан, если на пути к нему от его дома встретится более $m$ подряд идущих вершин с котами.

Ваша задача — помочь Кефе посчитать количество ресторанов, в которые он может безопасно пойти.

Вход. В первой строке заданы два целых числа $n$ и $m (2 \leq n \leq 1 0^{5}, 1 \leq m \leq n)$ — количество вершин дерева и максимальное количество подряд идущих вершин с котами, которое Кефа способен перенести.

Во второй строке содержится $n$ целых чисел $a_{1}, a_{2}, ..., a_{n}$ , где каждое $a_{i}$ равно либо $0$ (в вершине $i$ нет кота), либо $1$ (в вершине $i$ есть кот).

В следующих $n - 1$ строках перечислены ребра дерева в формате $x_{i} y_{i} (1 \leq x_{i}, y_{i} \leq n, x_{i} \neq = y_{i})$ , где $x_{i}$ и $y_{i}$ — вершины дерева, соединенные очередным ребром.

Гарантируется, что данный набор рёбер задаёт дерево.

Выход. Выведите количество листьев дерева, до которых Кефа сможет добраться, если на пути от его дома встречается не более $m$ подряд идущих вершин с котами.

Открыть задачу

Запустим поиск в глубину из вершины $1$ , где находится дом Кефы. В одном из параметров функции dfs будем хранить количество подряд идущих вершин с котами. Если в вершине $v$ это число превысит $m$ , дальнейший поиск в глубину из этой вершины не выполняем. Подсчитываем количество посещенных листьев. Вершина является листом, если ее степень равна $1$ и при этом она не является корнем (то есть вершиной $1$ ).

Пример

Рассмотрим деревья из первого и второго примеров.

В первом примере Кефа может пройти подряд только через одну вершину с котом. Он сможет попасть в рестораны, расположенные в вершинах $6$ и $7$ .

Во втором примере Кефа может пройти подряд только через две вершины с котами. Он сможет попасть в рестораны, расположенные в вершинах $4$ и $5$ .

Расположение котов храним в массиве $c a t s$ . Дерево храним в списке смежности $g$ .

vector<int> cats;
vector<vector<int> > g;

Функция dfs выполняет поиск в глубину из вершины $v$ и возвращает количество ресторанов, до которых можно добраться из этой вершины (при условии что на пути к ним встречается не более $m$ подряд идущих вершин с котами). Предком вершины $v$ является вершина $p re v$ . Количество подряд идущих вершин с котами, пройденных вплоть до вершины $v$ включительно, равно $c n t$ .

int dfs(int v, int prev, int cnt)
{

Если уже пройдено более $m$ котов подряд, то дальнейший поиск в глубину из вершины $v$ не продолжается.

  if (cnt > m) return 0;

Если мы находимся в листе, то увеличиваем количество ресторанов, в которые можно попасть.

  if (g[v].size() == 1 && prev != -1) return 1;

В переменной $res$ подсчитываем количество ресторанов, достижимых из вершины $v$ .

  int res = 0;

Перебираем все ребра $(v, t o)$ , исходящие из $v$ . Если вершина $t o$ является предком $v$ , то не совершаем переход в эту вершину.

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

Если в вершине $v$ нет кота, устанавливаем $c = 0$ . В противном случае присваиваем $c = c n t + 1$ . Переменная $c$ хранит количество подряд идущих вершин с котами до вершины $t o$ включительно.

      int c = (cats[to] == 0) ? 0 : cnt + 1;

Запускаем поиск в глубину из вершины $t o$ .

      res += dfs(to, v, c);
    }

Возвращаем результат.

  return res;
}

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

scanf("%d %d", &n, &m);
cats.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &cats[i]);

Строим дерево.

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

Выводим ответ. Функция dfs, вызванная из вершины $1$ , возвращает ответ на задачу. Поскольку у вершины $1$ нет предка, вторым параметром передадим значение $- 1$ . Стартовав из вершины $1$ , мы посетили $c a t s [1]$ котов.

printf("%d\n", dfs(1, -1, cats[1]));

Python реализация

def dfs(v, prev, cnt):

Если уже пройдено более $m$ котов подряд, то дальнейший поиск в глубину из вершины $v$ не продолжается.

  if cnt > m:
    return 0

Если мы находимся в листе, то увеличиваем количество ресторанов, в которые можно попасть.

  if len(g[v]) == 1 and prev != -1:
    return 1

В переменной $res$ подсчитываем количество ресторанов, достижимых из вершины $v$ .

  res = 0

  for to in g[v]:
    if to != prev:

      c = 0 if cats[to] == 0 else cnt + 1

Запускаем поиск в глубину из вершины $t o$ .

      res += dfs(to, v, c)

Возвращаем результат.

  return res

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

n, m = map(int, input().split())
cats = [0] + list(map(int, input().split()))

Строим дерево.

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

print(dfs(1, -1, cats[1]))

Задано дерево с $n$ вершинами. Вершина $1$ считается корнем. Между любыми двумя вершинами существует единственный путь.

Обозначим $d (i, j)$ как количество рёбер на пути от вершины $i$ до вершины $j$ .

Найдите количество таких пар вершин $(i, j)$ , для которых выполняется равенство:

d (i, j) = d (i, 1) - d (j, 1)

Вход. Первая строка содержит одно целое число $n (1 \leq n \leq 1 0^{5})$ — количество вершин в дереве.

Каждая из следующих $n - 1$ строк содержит по два целых числа — описание рёбер дерева: пары вершин, соединённых ребром.

Выход. Выведите одно целое число – количество таких пар $(i, j)$ , для которых выполняется $d (i, j) = d (i, 1) - d (j, 1)$ .

Открыть задачу

Условие $d (i, j) = d (i, 1) - d (j, 1)$ выполняется для каждой пары вершин $(i, j)$ , у которой $j$ является предком $i$ при поиске в глубину из вершины $1$ . Рассмотрим пример:

$d (4, 1) = 2, d (4, 1) - d (1, 1) = 2 - 0 = 2$ ;
$d (6, 3) = 2, d (6, 1) - d (3, 1) = 3 - 1 = 2$ ;
$d (2, 2) = 0, d (2, 1) - d (2, 1) = 1 - 1 = 0;$
$d (6, 1) = 3, d (6, 1) - d (1, 1) = 3 - 0 = 3;$

Глубиной $h [v]$ вершины $v$ назовем количество вершин на пути от корня (вершины $1$ ) до $v$ . На рисунке глубина указана возле каждой вершины.

Зафиксируем вершину $i$ и ответим на вопрос: сколько существует вершин $j$ , для которых выполняется условие $d (i, j) = d (i, 1) - d (j, 1)$ .

Например, для $i = 6$ существуют $4$ такие вершины: $j = 1, 3, 4, 6$ . Заметим, что $h [6] = 4$ . Таким образом, для фиксированной вершины $i$ существует ровно $h [i]$ подходящих вершин $j$ .

Для решения задачи необходимо для каждой вершины $v$ дерева вычислить её глубину $h [v]$ , а затем найти сумму всех значений глубин по дереву.

Пример

Рассмотрим граф из примера. Возле каждой вершины запишем ее глубину.

Сумма глубин всех вершин равна $1 + 2 + 3 + 3 + 4 = 13$ .

Объявим список смежности графа $g$ . Глубину вершин храним в массиве $h$ .

vector<vector<int> > g;
vector<int> h;

Функция dfs для каждой вершины $v$ вычисляет ее глубину. Предком вершины $v$ является вершина $p$ .

int dfs(int v, int p)
{
  for (int to : g[v])

Рассматриваем ребро $(v, t o)$ . Если вершина $t o$ не является предком вершины $v$ , вычисляем ее глубину и запускаем из нее поиск в глубину.

    if (to != p)
    {
      h[to] = h[v] + 1;
      dfs(to, v);
    }
  return h[v];
}

Основная часть программы. Читаем количество вершин дерева $n$ .

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

Строим дерево.

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

Глубину вершины $1$ положим равной $1$ .

h.resize(n + 1);
h[1] = 1;

Запускаем поиск в глубину, начиная с вершины $1$ .

dfs(1, -1);

Вычисляем ответ — сумму глубин всех вершин.

res = 0;
for (i = 1; i <= n; i++)
  res += h[i];

Выводим ответ.

printf("%lld\n", res);

Задано бинарное дерево — ациклический связный неориентированный граф, содержащий $n$ вершин и $n - 1$ ребро. Каждая вершина имеет степень не больше $3$ , а корнем является вершина с номером $1$ , причем её степень не превышает $2$ .

К сожалению, корень дерева заражён. Следующий процесс повторяется $n$ раз:

Хусейн либо выбирает ещё не заражённую (и не удалённую) вершину и удаляет её вместе со всеми инцидентными ей рёбрами, либо ничего не предпринимает.
После этого заражение распространяется на каждую вершину, соединённую ребром с уже заражённой вершиной (все ранее заражённые вершины остаются заражёнными).

Помогите Хусейну определить, какое максимальное количество вершин он может спасти от заражения (учтите, что удалённые вершины не считаются спасёнными).

Вход. Первая строка содержит количество вершин дерева $n (2 \leq n \leq 3 \cdot 1 0^{5})$ .

Каждая из следующих $n - 1$ строк содержит два числа $u_{i}$ и $v_{i} (1 \leq u_{i}, v_{i} \leq n)$ , обозначающих ребро дерева.

Гарантируется, что граф является бинарным деревом с корнем в вершине $1$ .

Выход. Выведите одно целое число — количество спасенных вершин.

Открыть задачу

Для каждой вершины $v$ вычислим количество вершин $s u m [v]$ в поддереве, где она является корнем. Если $t o_{1}, t o_{2}, ..., t o_{k}$ — сыновья вершины $v$ , то

s u m [v] = 1 + s u m [t o_{1}] + s u m [t o_{2}] + ... + s u m [t o_{k}]

Если вершина $v$ является листом дерева, то $s u m [v] = 1$ .

Пусть $d p [v]$ равно количеству спасенных вершин в поддереве с корнем $v$ , если на данный момент вершина $v$ (и только она в поддереве) заражена.

Если вершина $v$ имеет только одного сына $t o$ , то $d p [v] = s u m [t o] - 1$ (удаленная вершина $t o$ не является спасенной).

Пусть вершина $v$ имеет двух сыновей $t o_{1}$ и $t o_{2}$ (каждая вершина имеет степень не больше $3$ ). Тогда у нас имеется два варианта:

Удалить $t o_{1}$ и рекурсивно спасать вершины поддерева с корнем $t o_{2}$ . Число спасенных вершин составит $s u m [t o_{1}] - 1 + d p [t o_{2}]$ .
Удалить $t o_{2}$ и рекурсивно спасать вершины поддерева с корнем $t o_{1}$ . Число спасенных вершин составит $s u m [t o_{2}] - 1 + d p [t o_{1}]$ .

Из двух вариантов следует выбрать тот, при котором количество спасенных вершин будет большим.

Рассмотрим процесс поиска в глубину, когда рассматривается ребро $(v, t o)$ .

Пусть $a$ — второй сын вершины $v$ . Нам следует вычислить значение $d p [t o] + s u m [a] - 1$ . Попробуем его найти, используя только вершины $v$ и $t o$ . Нам известно, что

s u m [v] = 1 + s u m [t o] + s u m [a]

Откуда

s u m [a] = s u m [v] - s u m [t o] - 1

Следовательно

d p [t o] + s u m [a] - 1 = d p [t o] + s u m [v] - s u m [t o] - 2

Перебираем сыновей $t o$ вершины $v$ и вычисляем

d p [v] = ma x (d p [t o] + s u m [v] - s u m [t o] - 2)

Пример

В первом примере Хусейн сможет спасти две вершины $3$ и $4$ , выбрав своим первым ходом вершину номер $2$ .

Рассмотрим второй пример. Возле каждой вершины $v$ поставим метки $s u m [v] / d p [v]$ . Вершины, выбранные Хусейном, отобразим зеленым цветом.

Например,

d p [1] = ma x (s u m [2] - 1 + d p [5], s u m [5] - 1 + d p [2]) = ma x (2, 2) = 2, s u m [1] = 1 + s u m [2] + s u m [5] = 1 + 3 + 3 = 7

Объявим рабочие массивы.

#define MAX 300005
int sum[MAX], dp[MAX];
vector<vector<int>> g;

Функция dfs совершает поиск в глубину из вершины $v$ . Предком вершины $v$ является $p$ .

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

Инициализируем значения $s u m [v]$ и $d p [v]$ .

  sum[v] = 1;
  dp[v] = 0;

Запускаем поиск в глубину из сыновей вершины $v$ .

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

Вычисляем значение $d p [v]$ .

  for (int to : g[v])
    if (to != p)
    {
      dp[v] = max(dp[v], sum[to] - 1); // if 1 son
      dp[v] = max(dp[v], dp[to] + sum[v] - sum[to] - 2);
    }
}

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

scanf("%d", &n);
g.clear(); g.resize(n + 1);
memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum));
for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

Запускаем поиск в глубину из вершины $1$ .

dfs(1);

Выводим ответ.

printf("%d\n", dp[1]);

Список использованных задач

Комментарии (5)

user767927•1 месяц назад•2 ревизия

сайт розповідає з чого складається, як зробити

user897042•2 месяца назад

what a community i asked for help and noone cares.

user897042•2 месяца назад

https://codeforces.com/contest/315/problem/B how to solve this problem i wrote two updates one for assinging and second for interval with lazy. but it doesnt seem to work because two seperate updates doesnt have link between them.

medv•2 месяца назад

user897042 https://site.ada.edu.az/~medv/acm/Docs%20e-olimp/Volume%209/853_English.htm

user897042•2 месяца назад

user897042 need help on these two too:https://codeforces.com/contest/1857/problem/Ghttps://codeforces.com/contest/1702/problem/G

Загрузка

Момент, получаем данные с сервера