1 рік тому

Дерева

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

Дерево — це зв'язний, ациклічний, неорієнтований граф.

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

Зв'язність — між будь-якою парою вершин у графі існує шлях.
Ациклічність — граф не містить циклів.

У дереві з $n$ вершинами завжди рівно $n - 1$ n - 1 ребро.

Основні властивості дерева

1. Зв'язність і унікальність шляхів

У дереві між будь-якою парою вершин існує єдиний шлях.

2. Кількість ребер

Для будь-якого дерева:

∣ E ∣ = ∣ V ∣ - 1

|E| = |V| - 1

3. Відсутність циклів

Додавання навіть одного ребра до дерева завжди створює цикл.

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

Якщо одна вершина обрана як корінь, дерево стає орієнтованим від кореня до його нащадків. Це використовується у рекурсивних обходах та алгоритмах ( $D F S$ , $L C A$ та ін.).

5. Піддерева

Будь-яка вершина разом зі своїми нащадками утворює піддерево. Піддерево саме є деревом.

6. Листя

Вершини без нащадків (у кореневому дереві) називаються листям.

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

Глибина вершини — це відстань від кореня до цієї вершини.
Висота дерева — це максимальна глибина серед усіх вершин.

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

Центр — це вершина (або пара суміжних вершин), яка мінімізує максимальну відстань до всіх інших вершин.

Альтернативні визначення дерева

Наступні визначення дерева є еквівалентними і можуть використовуватись у різних контекстах:

Граф без циклів, який стає незв'язним при видаленні будь-якого ребра.
Зв'язний граф з $n$ вершинами і $n - 1$ n - 1 ребрами.
Ациклічний граф з $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) {}
};

C++

Загальне дерево:

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

Eolymp #977. Чи є граф деревом?

Задано неорієнтований граф без петель та кратних ребер у вигляді матриці суміжності. Визначте, чи є цей граф деревом.

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

Вихідні дані. Виведіть "YES", якщо граф є деревом, і "NO" в іншому випадку.

Відкрити задачу

Оголосіть матрицю суміжності графа $g$ та масив $u se d$ .

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

Функція dfs виконує обхід у глибину, починаючи з вершини $v$ . Вершина $p$ є батьківською для вершини $v$ . Якщо буде виявлено цикл, змінна $f l a g$ набуде значення $1$ .

void dfs(int v, int p)
{

Якщо граф уже не є деревом $(f l a g = 1)$ (flag = 1), продовжувати пошук немає сенсу.

  if (flag) return;

Позначимо вершину $v$ як відвідану.

  used[v] = 1;

Вершина $v$ відвідана, збільшуємо значення $c$ на $1$ .

  c++;

Ребро $(v, i)$ буде зворотним ребром та утворить цикл, якщо $i \neq = p$ i \ne p і вершина $i$ вже відвідана $(u se d [i] = 1)$ (used[i] = 1). Якщо цикл виявлено, встановлюємо $f l a g = 1$ flag = 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$ flag = 0, якщо цикл відсутній у графі. Якщо цикл виявлено, $f l a g$ набуде значення $1$ .

c = 0;
flag = 0;

Спочатку всі вершини не відвідані (ініціалізуємо масив $u se d$ нулями).

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

Починаємо обхід у глибину з вершини $0$ . Оскільки це корінь дерева, у неї немає батьківської вершини. Передаємо значення $- 1$ другим аргументом у функцію dfs.

dfs(0,-1);

Граф не є деревом, якщо є зворотне ребро $(f l a g = 1)$ (flag = 1) або якщо граф не зв'язний $(c \neq = n)$ (c \ne 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)$ (flag = 1), продовжувати пошук немає сенсу.

  if flag: return

Позначимо вершину $v$ як відвідану.

  used[v] = 1

Вершина $v$ відвідана, збільшуємо значення $c$ на $1$ .

  c += 1

Ребро $(v, i)$ буде зворотним ребром та утворить цикл, якщо $i \neq = p$ i \ne p та вершина $i$ вже відвідана $(u se d [i] = 1)$ (used[i] = 1). Якщо виявлено цикл, встановлюємо $f l a g = 1$ flag = 1. Якщо циклу немає, продовжуємо пошук з вершини $i$ .

  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$ . Встановлюємо $f l a g = 0$ flag = 0, якщо циклів немає у графі. Якщо цикл виявлено, $f l a g$ набуде значення $1$ .

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$ . Оскільки це корінь дерева, вона не має батьківської вершини. Передаємо значення $- 1$ другим аргументом до функції dfs.

dfs(0, -1)

Граф не є деревом, якщо існує зворотне ребро $(f l a g = 1)$ (flag = 1) або якщо граф не є зв'язним $(c \neq = n)$ (c \ne 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$ g[v][i] = 1;
Вершина $i$ ще не відвідана $(u se d [i] = 0)$ (used[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$ n - 1, а також якщо він зв'язний $(c = n)$ (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$ g[v][i] = 1;
Вершина $i$ ще не відвідана $(u se d [i] = 0)$ (used[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$ . Підраховуємо кількість ребер у графі.

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$ n - 1 та якщо він зв'язний $(c = n)$ (c = n).

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

Eolymp #978. Отримати дерево

Дано зв'язний неорієнтований граф без петель та кратних ребер. Дозволяється видаляти ребра графа. Потрібно отримати дерево.

Вхідні дані. У першому рядку записано два цілих числа — кількість вершин $n (1 \leq n \leq 100)$ n~(1 \le n \le 100) та кількість ребер $m$ у графі. Далі записано $m$ пар цілих чисел, що задають ребра. Гарантується, що граф зв'язний.

Вихідні дані. Виведіть $n - 1$ 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);
    }
}

C++

Основна частина програми. Зчитуємо вхідні дані.

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;
}

C++

Запускаємо обхід у глибину з першої вершини.

dfs(1);

Eolymp #11263. Парне дерево

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

Потрібно знайти максимальну кількість ребер, які можна видалити з дерева так, щоб отримати ліс, у якому кожна зв'язна компонента містить парну кількість вершин.

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

Вхідні дані. У першому рядку записано два цілих числа: кількість вершин $n (2 \leq n \leq 100, n$ n~(2 \le n \le 100, n — парне) та кількість ребер $m$ . У кожному з наступних $m$ рядків записано по два цілих числа — вершини, з'єднані ребром. Корінь дерева — вершина $1$ .

Вихідні дані. Виведіть максимальну кількість ребер, які можна видалити.

Відкрити задачу

Оголошуємо масиви.

#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$ . Додаємо значення, що повертає виклик $df s (i)$ , до змінної $s$ .

  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$ . У змінній $r es$ підраховуємо кількість видалених ребер.

res = 0;
dfs(1);

Оскільки немає ребра від вершини $1$ до її батьківської вершини, виводимо значення $r es - 1$ res - 1.

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

Реалізація на Python

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

У змінній $s$ обчислюємо кількість вершин у піддереві з коренем $v$ .

  s = 1

Перебираємо дочірні вершини $i$ вершини $v$ . Додаємо значення виклику $df s (i)$ до змінної $s$ .

  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

Python

Запускаємо обхід у глибину з вершини $1$ . У змінній $r es$ підраховуємо кількість видалених ребер.

res = 0
dfs(1)

Оскільки немає ребра від вершини $1$ до її батьківської вершини, виводимо значення $r es - 1$ res - 1.

print(res - 1)

Eolymp #11429. Підлеглі

Дано структуру компанії. Потрібно для кожного працівника порахувати кількість його підлеглих.

Вхідні дані. У першому рядку знаходиться ціле число $n (1 \leq n \leq 2 \cdot 1 0^{5})$ n~(1 \le n \le 2 \cdot 10^5) — кількість працівників. Працівники пронумеровані числами $1$ , $2$ , ..., $n$ , причому працівник номер $1$ є генеральним директором компанії.

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

Вихідні дані. Виведіть $n$ цілих чисел: для кожного працівника $1$ , $2$ , ..., $n$ кількість його підлеглих.

Відкрити задачу

Дерево зберігається у списку суміжності $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$ v \to to. Якщо $t o \neq = p$ to \ne 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$ sum[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();
  }
}

Java

Реалізація на Python

Збільшуємо розмір стеку для рекурсії.

import sys
sys.setrecursionlimit(1000000)

Функція dfs виконує обхід у глибину, починаючи з вершини $v$ , і повертає кількість вершин у піддереві з коренем $v$ . Вершина $p$ — це батьківська вершина для $v$ в обході у глибину.

def dfs(v, p):

Спочатку піддерево з коренем $v$ містить лише саму вершину $v$ .

  sum[v] = 1

Розглянемо ребро $v \to t o$ v \to to. Якщо $t o \neq = p$ to \ne 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 = 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)$ i~(i \ge 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$ sum[i] - 1.

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

Eolymp #11428. Діаметр дерева

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

Діаметром дерева називається максимальна відстань між двома вершинами. Знайдіть діаметр заданого дерева.

Вхідні дані. У першому рядку знаходиться ціле число $n (1 \leq n \leq 2 \cdot 1 0^{5})$ n~(1 \le n \le 2 \cdot 10^5) — кількість вершин у дереві. Вершини пронумеровані від $1$ до $n$ .

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

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

Відкрити задачу

Зберігаємо задане дерево у списку суміжності $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)
{

Зберігаємо найкоротшу відстань від початкової вершини до вершини $v$ у масиві $d i s t [v]$ dist[v].

  dist[v] = d;

Перебираємо всі ребра $(v, t o)$ (v, to). Для кожного сина $t o$ вершини $v$ (де $t o$ не є батьківською вершиною $v$ ) запускаємо обхід у глибину. Відстань від початкової вершини до вершини $t o$ буде $d + 1$ 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]);

Eolymp #11430. Відстані у дереві I

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

Для кожної вершини знайдіть максимальну відстань до будь-якої іншої вершини.

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

Наступні $n - 1$ n - 1 рядків описують ребра: кожен рядок містить два числа $a$ та $b (1 \leq a, b \leq n)$ b~(1 \le a, b \le n), що означає наявність ребра між вершинами $a$ та $b$ .

Вихідні дані. Виведіть $n$ цілих чисел. Для кожної вершини від $1$ до $n$ виведіть максимальну відстань до будь-якої іншої вершини дерева.

Відкрити задачу

Вхідне дерево зберігається у списку суміжності $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)
{

Зберігаємо найкоротшу відстань від початкової вершини до вершини $v$ в масиві $d i s t [v]$ dist[v].

  dist[v] = d;

Перебираємо всі ребра $(v, t o)$ (v, to). Для кожного сина $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):

Зберігаємо найкоротшу відстань до вершини $v$ в $d i s t [v]$ dist[v].

  dist[v] = d

Перебираємо всі вершини $t o$ , суміжні з $v$ , і виконуємо обхід у глибину, якщо $t o$ не є батьком $v$ .

  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:]))

Далі обчислимо найкоротші відстані від вершини $a$ і збережемо їх у масиві $d i s t a$ . Найвіддаленішою від $a$ виявляється вершина $b$ . Відстань між вершинами $a$ та $b$ є діаметром дерева.

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)

Eolymp #2157. Сума

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

Вхідні дані. У першому рядку задано ціле число $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) — кількість вершин у графі.

Кожен з наступних $n - 1$ n - 1 рядків описує ребро і містить три цілі числа: номери двох вершин, з'єднаних ребром (вершини пронумеровані від $1$ до $n$ ), та вагу ребра.

Вихідні дані. Виведіть загальну довжину всіх різних шляхів між усіма парами вершин, за модулем $1 0^{9}$ 10^9.

Відкрити задачу

Виконай пошук у глибину, починаючи з довільної вершини дерева. Розглянемо ребро $(u, v)$ з вагою $w$ . Нехай кількість вершин у піддереві з коренем у вершині $v$ дорівнює $c$ . Тоді по один бік ребра є $c$ вершин, а по інший — $n - c$ n - c. Ребро $(u, v)$ входить у $c \cdot (n - c)$ c \cdot (n - c) різних шляхів між парами вершин. Таким чином, його внесок у загальну довжину всіх шляхів становить $c \cdot (n - c) \cdot w$ c \cdot (n - c) \cdot w. Потрібно лише пройтися всіма ребрами за допомогою пошуку в глибину і підсумувати їхній внесок у загальну довжину всіх шляхів.

Приклад

Графи, наведені у прикладах, мають таку структуру:

Розглянемо внесок ребер у загальну довжину всіх шляхів у першому прикладі.

Ребро $(1, 2)$ з вагою $1$ входить до двох шляхів:

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

Його внесок у загальну суму: $1 \cdot 2 \cdot 1 = 2$ 1 \cdot 2 \cdot 1 = 2.

Ребро $(1, 3)$ з вагою $3$ входить до двох шляхів:

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

Його внесок у загальну суму: $2 \cdot 1 \cdot 3 = 6$ 2 \cdot 1 \cdot 3 = 6.

Загальна довжина всіх шляхів дорівнює $2 + 6 = 8$ 2 + 6 = 8.

У другому прикладі розглянемо внесок ребра $(1, 2)$ з вагою $5$ у загальну довжину всіх шляхів.

Кількість вершин у піддереві з коренем у вершині $2$ дорівнює $c = 4$ c = 4 (включаючи саму вершину $2$ ). Тоді з іншого боку ребра $(1, 2)$ знаходиться $n - c = 6 - 4 = 2$ n - c = 6 - 4 = 2 вершини. Отже, кількість різних шляхів, що проходять через ребро $(1, 2)$ , дорівнює $c \cdot (n - c) = 4 \cdot 2 = 8$ c \cdot (n - c) = 4 \cdot 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, 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

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

Задаємо значення модуля як $M O D$ .

#define MOD 1000000000

Вхідний зважений граф зберігається у вигляді списку суміжності $g$ .

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

Функція dfs виконує обхід у глибину, починаючи з вершини $v$ , і повертає кількість вершин у піддереві з коренем у $v$ (включаючи саму вершину $v$ ). Кількість таких вершин підраховується у змінній $c n t$ . Спочатку встановлюємо $c n t = 1$ cnt = 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;

C++

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

c \cdot (n - c) \cdot w

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;
}

C++

Основна частина програми. Зчитування вхідного зваженого графа у список суміжності $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});
}

C++

Запускаємо обхід у глибину з вершини $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());
  }
}

Java

Реалізація на Python

Оголосимо значення модуля як $M O D$ .

MOD = 1000000000

Функція dfs виконує обхід графа в глибину, починаючи з вершини $v$ , і повертає кількість вершин у піддереві з коренем у $v$ (включаючи $v$ ). Кількість таких вершин підраховується у змінній $c n t$ . Спочатку $c n t = 1$ cnt = 1, оскільки піддерево вже містить вершину $v$ .

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

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

c \cdot (n - c) \cdot w

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))

Python

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

dfs(1)

Виведення відповіді.

print(res)

Eolymp #2923. Tree

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

Вхідні дані. У першому рядку записано одне ціле число $n (1 \leq n \leq 1 0^{6})$ n~(1 \le n \le 10^6). Наступні $n$ рядків описують вершини дерева. $i$ -ий рядок містить два цілих числа $p_{i}$ p_i та $c_{i}$ c_i, де $p_{i}$ p_i — батько вершини $i$ , а $c_{i}$ c_i — колір вершини $i (1 \leq c_{i} \leq n)$ i~(1 \le c_i \le n). Для кореня дерева $p_{i} = 0$ p_i = 0.

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

Відкрити задачу

Масив $co l or [i]$ color[i] зберігає колір вершини $i$ . Множина $s [i]$ буде накопичувати кольори, що зустрічаються в піддереві з коренем у вершині $i$ .

Орієнтоване дерево представлено у вигляді списку суміжності $g$ . Масив $r es [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)$ (v, to).

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

Для кожного ребра $(v, t o)$ (v, to) об'єднуємо множину $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();
  }

Після цього зберігаємо кількість різних кольорів у піддереві в $r es [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;
}

C++

Почніть обхід у глибину з кореня дерева — вершини з індексом $0$ .

dfs(0);

Виведіть відповідь.

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

Eolymp #3983. Mancunian And Colored Tree

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

Щоб не нудьгувати, вони вирішили перевірити свою логіку. Коренем дерева є вершина $1$ . Для кожної вершини учасники вирішили знайти її найближчого предка такого ж кольору.

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

Друга строка містить $n - 1$ n - 1 ціле число: $i$ -те з них вказує батька вершини $i + 1$ i + 1.

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

Вихідні дані. Виведіть $n$ цілих чисел в одному рядку: для кожної вершини виведіть номер її найближчого предка з таким самим кольором. Якщо такого предка не існує, виведіть $- 1$ .

Відкрити задачу

Розглянемо спрощену версію задачі. Нехай усі вершини дерева пофарбовані в один і той самий колір. Ініціалізуємо порожній стек і виконуємо обхід у глибину з кореня дерева. При вході у вершину $v$ додаємо її до стеку. Коли обробка вершини $v$ завершується, видаляємо з вершини стеку елемент (ним буде $v$ ). Після завершення DFS стек знову буде порожнім.

Питання: Що буде на вершині стеку в момент входу у вершину $v$ , безпосередньо перед її додаванням?

Тепер перейдемо до розв'язку оригінальної задачі. Створимо $c$ стеків — по одному для кожного кольору (наприклад, у вигляді вектора стеків). Спочатку всі стеки порожні. Виконуємо обхід у глибину з кореня дерева — вершини $1$ . Обробка вершини $v$ , пофарбованої у колір $co l or$ , включає наступні кроки:

Якщо стек $s [co l or]$ s[color] не порожній, його верхній елемент містить номер вершини, яка є найближчим предком вершини $v$ того ж кольору. Якщо стек порожній, такої вершини не існує, і відповідь для $v$ дорівнює $- 1$ .
Додаємо вершину $v$ до стеку $s [co l or]$ s[color].
Рекурсивно виконуємо DFS для всіх дітей вершини $v$ .
Після завершення обробки вершини $v$ , видаляємо її зі стеку $s [co l or]$ s[color].

Під час обходу в глибину, коли ми перебуваємо у вершині $v$ , стеки містять інформацію про кольори всіх вершин на унікальному шляху від кореня до вершини $v$ . Зокрема, стек $s [co l or]$ s[color] зберігає номери всіх вершин на цьому шляху, пофарбованих у колір $co l or$ . Ці вершини додаються до стеку в порядку відвідування DFS.

Приклад

Коли обхід у глибину досягає вершини $5$ , два з $c = 4$ 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$ того ж кольору зберігається у $r es [v]$ .

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

Додаємо вершину $v$ до стеку, що відповідає її кольору.

  s[color].push(v);

Проходимо всіх нащадків $t o$ вершини $v$ і рекурсивно викликаємо обхід у глибину для кожного з них.

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

Після завершення обробки вершини $v$ (тобто при виході з неї) видаляємо її зі стеку, що відповідає її кольору.

  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);
}

C++

Зчитуємо кольори вершин дерева.

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$ того ж кольору зберігається у $r es [v]$ .

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

Додаємо вершину $v$ до стеку, що відповідає її кольору.

  s[color].append(v)

Ітеруємо по всіх нащадках $t o$ вершини $v$ та рекурсивно виконуємо обхід у глибину для кожного з них.

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

Після завершення обробки вершини $v$ (тобто після виходу з неї) видаляємо її зі стеку відповідного кольору.

  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:])

Eolymp #10422. MooTube (Silver)

У вільний час фермер Джон створив власну платформу для поширення відео під назвою MooTube. На MooTube його корови можуть записувати, публікувати та переглядати багато смішних відео. На цей момент корови завантажили $n$ відео, пронумерованих від $1$ до $n$ .

Проте фермер Джон не до кінця розуміє, як допомогти своїм коровам знаходити нові відео, які їм можуть сподобатися. Він хоче реалізувати систему рекомендацій для кожного відео — список «рекомендованих відео» на основі їхньої схожості з уже переглянутими.

Щоб визначити, наскільки два відео схожі, Джон вводить метрику релевантності. Він вручну оцінює $n - 1$ n - 1 пар відео та призначає кожній парі певну оцінку релевантності. Використовуючи ці пари, Джон будує мережу, де кожне відео — це вершина в графі, а обрані пари з'єднані ребрами з відповідними значеннями релевантності.

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

Він вирішує, що релевантність між двома відео має визначатися як мінімальне значення релевантності серед усіх ребер на шляху, що з'єднує ці два відео.

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

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

Вхідні дані. Перша стрічка містить два цілі числа $n$ та $q (1 \leq n, q \leq 5000)$ q~(1 \le n, q \le 5000) — кількість відео та кількість запитів відповідно.

Наступні $n - 1$ n − 1 стрічок описують пари відео, релевантність яких була вручну оцінена фермером Джоном. Кожна з цих стрічок містить три цілі числа $p_{i}, q_{i}$ p_i, q_i та $r_{i} (1 \leq p_{i}, q_{i} \leq n, 1 \leq r_{i} \leq 1 0^{9})$ r_i~(1 \le p_i, q_i \le n, 1 \le r_i \le 10^9), що означає, що відео $p_{i}$ p_i та $q_{i}$ q_i з'єднані ребром із релевантністю $r_{i}$ r_i.

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

Вихідні дані. Виведіть $q$ стрічок. У $i$ -тій стрічці виведіть відповідь на $i$ -тий запит фермера Джона.

Приклад. Фермер Джон встановив наступні зв'язки між відео:

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

На основі цих даних можемо обчислити релевантність між іншими парами відео:

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

Розглянемо, які відео будуть рекомендовані для наступних запитів:

Для відео $2$ при $k = 1$ k = 1, будуть рекомендовані відео $1$ , $3$ та $4$ .
Для відео $1$ при $k = 3$ k = 3, будуть рекомендовані відео $2$ та $4$ .
Для відео $1$ при $k = 4$ 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$ used[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$ ) рахуємо у змінній $r es$ .

  int res = 0;

Починаємо обхід у ширину.

  while (!q.empty())
  {

Виймаємо вершину $v$ з черги $q$ .

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

Ітеруємося по всіх ребрах, інцидентних вершині $v$ .

    for (auto edge : g[v])
    {

Розглянемо ребро $(v, t o)$ (v, to) з вагою $k t o$ .

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

Якщо вага ребра $k t o$ менша за $k$ , пропускаємо це ребро (перехід по ньому заборонено).

      if (kto < k) continue;

Якщо вершина $t o$ ще не відвідана, додаємо її до черги, позначаємо як відвідану і збільшуємо лічильник $r es$ на $1$ .

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

C++

Повертаємо відповідь на запит.

  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);

Виконуємо пошук у ширину (BFS), починаючи з вершини $v$ , і виводимо кількість вершин, відвіданих під час BFS.

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

Реалізація алгоритму — пошук у глибину (DFS)

Зберігаємо вхідний граф у вигляді списку суміжності $g$ .

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

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

int dfs(int v, int k)
{

Позначаємо вершину $v$ як відвідану.

  used[v] = 1;

Змінна $r es$ зберігає кількість вершин, відвіданих у піддереві з коренем у $v$ під час DFS.

  int res = 1;

Ітеруємося по всіх ребрах, інцидентних вершині $v$ .

  for (auto edge : g[v])
  {

Розглядаємо ребро $(v, t o)$ (v, to) з вагою $k t o$ .

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

Якщо вага $k t o$ менша за $k$ , пропускаємо це ребро (перехід по ньому заборонений).

    if (kto < k) continue;

Якщо вершина $t o$ ще не відвідана, виконуємо пошук у глибину з неї. Кількість відвіданих вершин у піддереві з коренем у $t o$ додається до $r es$ .

    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$ . Виводимо кількість вершин, відвіданих під час DFS, виключаючи саму вершину $v$ .

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

Eolymp #10653. XOR Sum

Задано дерево з $n$ вершинами. Ребра дерева мають вагу лише $0$ або $1$ . Потрібно знайти XOR-суму для всіх пар вершин. Обчисліть суму всіх таких XOR-сум.

Вхідні дані. У першому рядку задано число вершин $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) у графі. Наступні $n - 1$ n - 1 рядків описують ребра. Кожен рядок містить три цілих числа — номери вершин, які з'єднує ребро (вершини нумеруються від $1$ до $n$ ), та вагу ребра ( $0$ або $1$ ).

Вихідні дані. Виведіть суму XOR-сум між усіма парами вершин.

Відкрити задачу

Збережемо граф у вигляді списку суміжності $g$ . Оголосимо масив $x$ .

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

Функція dfs виконує обхід у глибину та обчислює XOR-суму $x [v]$ від вершини $1$ до $v$ . Поточна сума XOR задається як $c u r_x or$ cur\_xor. Батьківська вершина $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);
  }
}

C++

Основна частина програми. Зчитування графа.

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});
}

C++

Запускаємо DFS з вершини $1$ .

dfs(1, 0, -1);

Підраховуємо кількість нулів та одиниць у масиві $x$ .

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

Виводимо відповідь.

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

Реалізація на Python

Функція dfs реалізує обхід у глибину (DFS), який обчислює XOR-суму $x [v]$ між вершинами $1$ та $v$ . Поточна XOR-сума між $1$ та $v$ представлена як $c u r_x or$ cur\_xor. Батьківська вершина $v$ — це $p$ .

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)

Запускаємо DFS з вершини $1$ .

dfs(1)

Обчислюємо кількість нулів і одиниць у масиві $x$ .

ones = sum(x)
zeroes = n - ones

Виводимо відповідь.

print(ones * zeroes)

Eolymp #10654. Унікальний колір

Задано дерево з $n$ вершинами, пронумерованими від $1$ до $n$ . $i$ -те ребро дерева з'єднує вершини $a_{i}$ a_i та $b_{i}$ b_i. Вершина $i$ пофарбована в колір $c_{i}$ c_i (у цій задачі кольори задані цілими числами).

Вершина $x$ вважається хорошою, якщо найкоротший шлях від вершини $1$ до вершини $x$ не містить жодної іншої вершини такого самого кольору, як і у вершини $x$ , крім самої $x$ .

Знайдіть усі хороші вершини.

Вхідні дані. У першому рядку міститься одне ціле число $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) — кількість вершин.

У другому рядку міститься $n$ цілих чисел — кольори вершин: $c_{1}, c_{2}, \dots, c_{n} (1 \leq c_{i} \leq 1 0^{5})$ c_1, c_2, \dots, c_n~(1 \le c_i \le 10^5).

Кожен з наступних $n - 1$ n - 1 рядків містить по два цілих числа $a_{i}$ a_i та $b_{i} (1 \leq a_{i}, b_{i} \leq n)$ b_i~(1 \le a_i, b_i \le n) — ребра дерева.

Вивід. Виведіть усі хороші вершини по одній у рядку в порядку зростання їхніх номерів.

Відкрити задачу

Збережемо вхідний граф у вигляді списку суміжності $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]$ color[v]. Позначимо, що вершина з цим кольором зустрічається на шляху від вершини $1$ .

  used[color[v]]++;

Значення $u se d [co l or [v]]$ used[color[v]] показує, скільки разів колір $co l or [v]$ color[v] з'являється на шляху від вершини $1$ до вершини $v$ (включно). Якщо цей колір зустрічається рівно один раз, тоді вершина $v$ вважається хорошою, і ми додаємо її до множини результату $s t$ .

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

Пройдемося по всіх ребрах $(v, t o)$ (v, to), що виходять з вершини $v$ . Якщо вершина $t o$ не є батьком $v (t o \neq = p a r)$ v~(to \ne par), запускаємо обхід у глибину з вершини $t o$ . У такому випадку, батьком вершини $t o$ стає вершина $v$ .

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

Після виходу з вершини $v$ зменшуємо значення $u se d [co l or [v]]$ used[color[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);
}

C++

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

dfs(1, 1);

Виводимо хороші вершини. Вони зберігаються в множині $s t$ .

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

Eolymp #10655. Virus Tree 2

Задано дерево з $n$ вершинами та $n - 1$ n − 1 ребром. Вершини пронумеровані від $1$ до $n$ , і $i$ -те ребро з'єднує вершини $a_{i}$ a_i та $b_{i}$ b_i.

У вас є $k$ кольорів. Для кожної вершини дерева потрібно вибрати один із $k$ кольорів, дотримуючись наступної умови:

Якщо відстань між двома різними вершинами $x$ та $y$ менша або дорівнює двом, то $x$ та $y$ повинні бути пофарбовані в різні кольори.

Скількома способами можна розфарбувати дерево? Знайдіть відповідь за модулем $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані. Перший рядок містить два числа $n$ та $k (1 \leq n, k \leq 1 0^{5})$ k~(1 \le n, k \le 10^5). Кожен з наступних $n - 1$ n - 1 рядків містить два цілих числа $a_{i}$ a_i та $b_{i} (1 \leq a_{i}, b_{i} \leq n)$ b_i~(1 \le a_i, b_i \le n).

Вихідні дані. Виведіть кількість способів розфарбувати дерево за модулем $1 0^{9} + 7$ 10^9 + 7

Відкрити задачу

Зберігаємо вхідний граф у списку суміжності $g$ . Оголошуємо константу $M O D$ для обчислення по модулю.

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

Функція dfs повертає кількість способів розфарбувати дерево з коренем у вершині $v$ за модулем $M O D = 1 0^{9} + 7$ MOD = 10^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$ cnt = 1, бо діти не можуть мати такий самий колір, як у $v$ . Якщо $v$ має батька ( $p \neq = - 1$ p \ne -1), то діти також не можуть мати колір батька.

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

Ітеруємось по синах $t o$ вершини $v$ .

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

Вершину $t o$ можна розфарбувати $k - c n t$ k - cnt кольорами. При переході до кожного сина значення $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);
}

C++

Починаємо обхід у глибину з вершини $1$ . Вершину номер $1$ можна розфарбувати $k$ кольорами.

res = dfs(1, k);

Виводимо відповідь.

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

Реалізація на Python

Встановлюємо максимальну глибину стеку інтерпретатора Python до вказаного ліміту.

import sys
sys.setrecursionlimit(1000000)

Оголошуємо константу $M O 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:

      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)

Eolymp #10684. Поліпшення доріг

У країні є $n$ міст і $n - 1$ n - 1 двосторонніх доріг, так що можливо дістатися з будь-якого міста до будь-якого іншого, використовуючи лише ці дороги. Міста пронумеровані цілими числами від $1$ до $n$ включно.

Спочатку всі дороги вважаються поганими, але уряд планує покращити стан деяких із них. Громадяни будуть задоволені покращенням, якщо на шляху від столиці, розташованої у місті $1$ , до будь-якого іншого міста буде не більше ніж одна погана дорога.

Визначте кількість способів покращити якість деяких доріг, щоб задовольнити цю вимогу. Оскільки відповідь може бути дуже великою, виведіть її по модулю $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані. У першому рядку задано одне ціле число $n (2 \leq n \leq 2 \cdot 1 0^{5})$ n~(2 \le n \le 2 \cdot 10^5) — кількість міст у країні. У другому рядку задано $n - 1$ n - 1 додатних цілих чисел $p_{2}, p_{3}, p_{4}, \dots, p_{n} (1 \leq p_{i} \leq i - 1)$ p_2, p_3, p_4, \cdots, p_n~(1 \le p_i \le i - 1), що описують дороги в країні. Число $p_{i}$ p_i означає, що є дорога між містом $p_{i}$ p_i та містом $i$ .

Вихідні дані. Виведіть кількість способів покращити якість доріг по модулю $1 0^{9} + 7$ 10^9 + 7.

Відкрити задачу

Усі обчислення виконуються по модулю $M O D = 1 0^{9} + 7$ MOD = 10^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}$ to_1, to_2, ..., to_k — діти вершини $v$ , то

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

f(v) = (f(to_1) + 1) \cdot (f(to_2) + 1) \cdot ... \cdot (f(to_k) + 1)

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

C++

Зчитуємо вхідні дані. Побудова дерева.

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);
}

C++

Обчислюємо та виводимо результат.

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

Eolymp #11058. Наздоганяючи метелика

У ясні літні дні Нюша полюбляє ловити метеликів на свіжому повітрі. Але сьогодні їй трапився особливо хитрий метелик — він залетів до лабіринту й намагається сховатися в ньому.

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

Вхід до лабіринту розташований у кімнаті номер $1$ . Листом називається будь-яка кімната, яка з'єднана лише з однією іншою кімнатою і не є коренем (тобто не є кімнатою $1$ ). У кожному листі є вихід із лабіринту. Метелик починає свій політ із кімнати $1$ в напрямку одного з виходів. Він рухається з сталою швидкістю, ніколи не повертається назад і проходить один коридор за хвилину, переходячи в сусідню кімнату. Усі коридори однакової довжини.

Щоб зловити метелика, Нюша вирішила покликати на допомогу кількох друзів. Спочатку кожен з них може зайняти позицію в будь-якій кімнаті, де є вихід. Щойно метелик почне свій рух із входу в напрямку будь-якого виходу, друзі одразу можуть почати рух з виходів у напрямку до входу. Вони рухаються з тією ж швидкістю, що й метелик. Якщо хтось із них зустріне метелика — чи то в кімнаті, чи посередині коридору — вважається, що його спіймано. Якщо ж метелик досягне виходу, не зустрівши жодного з друзів, він успішно втече на волю.

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

Вхідні дані. Перший рядок містить одне ціле число $n (2 \leq n \leq 200000)$ n~(2 \le n \le 200000) — кількість кімнат у лабіринті.

Наступні $n - 1$ n - 1 рядків описують коридори, які з'єднують кімнати. Кожен рядок містить два цілих числа $u$ та $v (1 \leq u, v \leq n, u \neq = v)$ v~(1 \le u, v \le n, u \ne v) — номери кімнат, з'єднаних коридором.

Гарантується, що задана система коридорів утворює дерево.

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

Відкрити задачу

Виконаємо обхід у глибину (DFS), починаючи з вершини $1$ . Для кожної вершини обчислюємо два значення:

$d [v]$ — відстань від вершини $1$ до вершини $v$ . Якщо $p$ — батько вершини $v$ , то
$d [v] = d [p] + 1$
d[v] = d[p] + 1
$h [v]$ — відстань від вершини $v$ до найближчого листа в піддереві з коренем у $v$ . Якщо $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — діти вершини $v$ , то
$h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])$
h[v] = 1 + \min(h[to_1], h[to_2], ..., h[to_k])
Якщо $v$ — лист дерева, то покладаємо $h [v] = 0$ h[v] = 0.

Далі виконаємо другий обхід у глибину. Під час цього проходу обчислюється значення $r es [v]$ — мінімальна кількість друзів, яких потрібно розмістити в деяких листах піддерева з коренем у вершині $v$ , щоб гарантовано спіймати метелика, якщо він вирішить летіти саме в це піддерево.

Якщо $h [v] \leq d [v]$ h[v] \le d[v], то $r es [v] = 1$ res[v] = 1. У цьому випадку достатньо одного друга, якого можна розмістити в листі з мінімальною глибиною в піддереві вершини $v$ : він дійде до вершини $v$ не пізніше, ніж метелик, що летить із кореня.

Інакше, якщо $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — діти вершини $v$ , тоді

r es [v] = r es [t o_{1}] + r es [t o_{2}] + \dots + r es [t o_{k}]

res[v] = res[to_1] + res[to_2] + \ldots + res[to_k]

Якщо метелика не вдається спіймати безпосередньо у вершині $v$ , то потрібно бути готовим перехопити його в будь-якому з піддерев дітей $v$ .

Остаточна відповідь до задачі — це значення $r es [1]$ .

Приклад

У першому прикладі (лівий малюнок) потрібно два друга, які мають бути розміщені біля двох виходів. Метелик може летіти з вершини $1$ або до вершини $2$ , або до вершини $3$ . В обох випадках його перехопить один із друзів Нюші.

У другому прикладі (правий малюнок) достатньо одного друга, якого можна розмістити або в вершині $3$ , або в вершині $4$ . Метелик за одну хвилину долетить до вершини $2$ , і за цей самий час друг дійде до неї з виходу та перехопить метелика.

Розглянемо наступний приклад.

Нюші знадобиться троє друзів, щоб спіймати метелика.

Оголосимо константу для нескінченності та масиви.

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

Функція dfs $(v, p, c n t)$ (v, p, cnt) виконує обхід у глибину, починаючи з вершини $v$ , і повертає значення $h [v]$ . Тут $p$ — батько вершини $v$ , а $c n t$ — відстань від вершини $1$ до вершини $v$ . Під час обходу обчислюються значення $d [v]$ та $h [v]$ для кожної вершини $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$ v \to to. Якщо $t o$ збігається з батьком вершини $v (t o = p)$ v~(to = p), пропускаємо його і переходимо до наступної вершини.

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

У змінній $h e i g h t$ обчислюємо значення

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

\min(h[to_1], h[to_2], \ldots, h[to_k]),

де $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — діти вершини $v$ .

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

h[v] = 1 + min(h[to_1], h[to_2], ..., h[to_k])

Якщо $h e i g h t = I N F$ height = INF, тоді вершина $v$ є листком, і встановлюємо $h [v] = 0$ h[v] = 0. Інакше повертаємо

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

h[v] = 1 + min(h[to_1], h[to_2], ..., h[to_k])

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

Функція dfs2 $(v, p)$ виконує обхід у глибину, починаючи з вершини $v$ , і повертає значення $r es [v]$ . Тут $p$ — це батьківська вершина для вершини $v$ .

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

Нехай $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — нащадки вершини $v$ . У змінній $s$ обчислюємо суму:

r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}]

res[to_1] + res[to_2] + ... + res[to_k]

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

Якщо $h [v] \leq d [v]$ h[v] \le d[v], то одного друга достатньо, і $r es [v] = 1$ res[v] = 1. Інакше

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

res[v] = res[to_1] + res[to_2] + ... + res[to_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);
}

C++

Ініціалізація масивів.

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

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

dfs(1);
dfs2(1);

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

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

Eolymp #11153. Kefa and Park

Кефа вирішив відсвяткувати свою першу велику зарплату походом до ресторану.

Він живе поруч із незвичним парком. Парк представляє собою укорінене дерево з $n$ вершинами, вкорінене у вершині $1$ . Дім Кефи також знаходиться у вершині $1$ . На жаль, у цьому парку мешкають коти, і Кефа вже визначив вершини, в яких ці коти знаходяться.

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

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

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

У другому рядку міститься $n$ цілих чисел $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n, де кожне $a_{i}$ a_i дорівнює $0$ (у вершині $i$ немає кота) або $1$ (у вершині $i$ є кіт).

У наступних $n - 1$ n - 1 рядках описано ребра дерева у форматі $x_{i} y_{i} (1 \leq x_{i}, y_{i} \leq n, x_{i} \neq = y_{i})$ x_i~y_i~(1 \le x_i, y_i \le n, x_i \ne y_i), де $x_{i}$ x_i і $y_{i}$ y_i — вершини, з’єднані ребром.

Гарантується, що задана множина ребер утворює дерево.

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

Відкрити задачу

Місця знаходження котів зберігаються в масиві $c a t s$ . Дерево зберігається у вигляді списку суміжності $g$ .

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

Функція dfs виконує обхід у глибину з вершини $v$ і повертає кількість ресторанів, до яких можна дістатися з цієї вершини (за умови, що на шляху до них трапляється не більше ніж $m$ послідовних вершин із котами). Батьківська вершина вершини $v$ — це вершина $p r e 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;

У змінній $r es$ рахуємо кількість ресторанів, доступних з вершини $v$ .

  int res = 0;

Перебираємо всі ребра $(v, t o)$ (v, to), що виходять із вершини $v$ . Якщо вершина $t o$ є батьківською для $v$ , не переходимо в неї.

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

Якщо у вершині $v$ немає кота, присвоїти c = 0. Інакше присвоїти c = cnt + 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);
}

C++

Вивести результат. Функція dfs, викликана з вершини $1$ , повертає відповідь на задачу. Оскільки вершина $1$ не має батьківської, другим параметром передаємо значення $- 1$ . Стартуючи з вершини $1$ , ми вже зустріли $c a t s [1]$ котів.

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

Реалізація мовою Python

Функція dfs виконує обхід у глибину з вершини $v$ і повертає кількість ресторанів, до яких можна дістатися з цієї вершини (за умови, що на шляху до них зустрічається не більше ніж $m$ послідовних вершин із котами). Батьківська вершина вершини $v$ — це $p r e v$ . Кількість послідовних вершин із котами до вершини $v$ включно — це $c n t$ .

def dfs(v, prev, cnt):

Якщо вже зустрілося більше ніж $m$ послідовних котів, подальший обхід у глибину з вершини $v$ не виконується.

  if cnt > m:
    return 0

Якщо ми знаходимося в листковій вершині, збільшуємо кількість доступних ресторанів.

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

У змінній $r es$ підраховується кількість ресторанів, до яких можна дістатися з вершини $v$ .

  res = 0

Проітеруємо всі ребра (v, to), що виходять з вершини $v$ . Якщо вершина $t o$ є батьківською для $v$ , не переходимо до неї.

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

Якщо у вершині $v$ немає кота, встановити c = 0. Інакше присвоїти c = cnt + 1. Змінна $c$ зберігає кількість послідовних вершин із котами до та включно вершини $t o$ .

      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)

Вивести результат. Функція dfs, викликана з вершини $1$ , повертає відповідь на задачу. Оскільки вершина $1$ не має батьківської, другим параметром передаємо значення $- 1$ . Починаючи з вершини $1$ , ми вже зустріли $c a t s [1]$ котів.

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

Eolymp #11609. Пошук пар

Задано дерево з $n$ вершинами. Вершина $1$ вважається коренем. Існує рівно один простий шлях між будь-якими двома вершинами.

Позначимо d(i, j) — кількість ребер на шляху від вершини $i$ до вершини $j$ .

Знайдіть кількість пар вершин $(i, j)$ таких, що виконується рівність:

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

Вхідні дані. Перший рядок містить одне ціле число n~(1 \le n \le 10^5) — кількість вершин у дереві.

Кожен з наступних n - 1 рядків містить по два цілих числа, які описують ребра дерева: пари вершин, з'єднаних ребром.

Вихідні дані. Виведіть одне число — кількість пар $(i, j)$ , для яких виконується d(i, j) = d(i, 1) - d(j, 1).

Open problem

Визначимо список суміжності графа як $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, to). Якщо вершина $t o$ не є батьком вершини $v$ , тоді обчислюємо її глибину та викликаємо dfs для неї.

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

C++

Основна частина програми. Зчитуємо кількість вершин $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);

Eolymp #11724. Інфіковане дерево

Дано бінарне дерево, яке є ациклічним зв'язним неорієнтованим графом з $n$ вершинами та n - 1 ребрами. Кожна вершина має степінь не більше $3$ . Коренем є вершина номер $1$ , при цьому її степінь не перевищує $2$ .

На жаль, корінь дерева інфікований. Наступний процес повторюється $n$ разів:

Гусейн або вибирає вершину, яка ще не інфікована (і ще не видалена), та видаляє її разом з усіма інцидентними їй ребрами, або не робить нічого.
Після цього інфекція поширюється на всі вершини, з'єднані ребром з уже інфікованими вершинами (усі раніше інфіковані вершини залишаються інфікованими).

Допоможіть Гусейну визначити максимальну кількість вершин, які він може врятувати від інфекції (зауважимо, що видалені вершини не вважаються врятованими).

Вхідні дані. У першому рядку міститься число n~(2 \le n \le 3 \cdot 10^5) — кількість вершин у дереві.

Кожен з наступних n - 1 рядків містить два цілих числа u_i та v_i~(1 \le u_i, v_i \le n) — ребро дерева.

Гарантується, що граф є бінарним деревом з коренем у вершині $1$ .

Вихідні дані. Виведіть одне ціле число — кількість врятованих вершин.

Відкрити задачу

Для кожної вершини $v$ обчислимо кількість вершин $s u m [v]$ у піддереві, де вона є коренем. Якщо to_1, to_2, ..., to_k — діти вершини $v$ , тоді

sum[v] = 1 + sum[to_1] + sum[to_2] + \dots + sum[to_k]

Якщо вершина $v$ є листком дерева, то sum[v] = 1.

Нехай $d p [v]$ — це кількість врятованих вершин у піддереві з коренем у $v$ , за умови, що наразі інфікована тільки вершина $v$ (і ніхто більше з піддерева не інфікований).

Якщо у вершини $v$ лише одна дитина $t o$ , тоді dp[v] = sum[to] - 1 (видалена вершина $t o$ не вважається врятованою).

Нехай вершина $v$ має двох дітей to_1 та to_2 (оскільки кожна вершина має степінь не більше $3$ ). Маємо два варіанти:

Видалити to_1 і рекурсивно рятувати вершини в піддереві з коренем to_2. Кількість врятованих вершин: sum[to_1] - 1 + dp[to_2].
Видалити to_2 і рекурсивно рятувати вершини в піддереві з коренем to_1. Кількість врятованих вершин: sum[to_2] - 1 + dp[to_1].

Серед двох варіантів вибираємо той, що дає більше врятованих вершин.

Розглянемо процес пошуку в глибину при обробці ребра (v, to).

Нехай $a$ — другий син вершини $v$ . Нам потрібно обчислити значення dp[to] + sum[a] - 1. Спробуймо знайти його, використовуючи лише вершини $v$ і $t o$ . Ми знаємо, що:

sum[v] = 1 + sum[to] + sum[a]

Звідси випливає, що:

sum[a] = sum[v] - sum[to] - 1

Таким чином,

dp[to] + sum[a] - 1 = dp[to] + sum[v] - sum[to] - 2

Проходимо по всіх дітях $t o$ вершини $v$ і обчислюємо:

dp[v] = \max(dp[to] + sum[v] - sum[to] - 2)

Приклад

У першому прикладі Гусейн може врятувати дві вершини — $3$ та $4$ , якщо вибере вершину $2$ для видалення.

Розглянемо другий приклад. Поряд з кожною вершиною $v$ вказано позначення sum[v] / dp[v]. Зеленим кольором позначені вершини, які видаляє Гусейн.

Наприклад,

dp[1] = \max(sum[2] - 1 + dp[5],\ sum[5] - 1 + dp[2]) = \max(2,\ 2) = 2, \\ sum[1] = 1 + sum[2] + sum[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); // якщо є лише один син
      dp[v] = max(dp[v], dp[to] + sum[v] - sum[to] - 2);
    }
}

C++

Основна частина програми. Зчитування вхідних даних.

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);
}

C++

Виконаємо обхід у глибину, починаючи з вершини $1$ .

dfs(1);

Виведемо відповідь.

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

Дерева

Основні властивості дерева

Альтернативні визначення дерева

Представлення дерев у коді

Список задач

Коментарі5