Условие задачи
На дереве живут термиты. Ваша задача убить их всех. Дерево является неориентированным связным графом с $n$ вершинами и $n — 1$ ребрами. Чтобы убить термитов, Вам следует отравить некоторые вершины. Если термит попадает на вершину с ядом, то он немедленно умирает. Вы не знаете, где изначально находятся термиты. Но Вы знаете, что термиты каждый раз попадают в случайную соседнюю вершину. Однако если термит прошел ребро $(u, v)$, то следующее ребро должно отличаться от $(v, u)$ за исключением случая, когда термит попадает в лист (в этом случае термит поворачивается и возвращается назад). Вам следует отравить минимальное количество вершин так, чтобы термиты попали в отравленные вершины после конечного числа шагов.
Входные данные
Первая строка содержит одно целое число $n$ $(1 \leqslant n \leqslant 100000)$. Следующая строка содержит $n — 1$ целое число $p_{i} (2 \leqslant i \leqslant n)$, означающее что ребро соединяет $p_{i}$ и $i$.
Выходные данные
Выведите минимальное количество отравленных вершин.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 1 | 1 |
| 2 | 2 1 |
1 |
| 3 | 8 1 1 2 1 2 3 2 |
2 |
| 4 | 5 1 2 1 4 |
1 |
| 5 | 16 1 2 3 4 5 3 7 1 9 9 11 11 13 13 15 |
3 |
| 6 | 10 1 2 3 3 1 2 3 7 9 |
2 |
| 7 | 8 1 1 3 3 1 6 6 |
2 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static final int NMAX = 100001; static ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>> (NMAX); static ArrayList<Integer> killed = new ArrayList<Integer> (NMAX); static ArrayList<Boolean> used = new ArrayList<Boolean> (NMAX); static ArrayList<Integer> dist = new ArrayList<Integer> (NMAX); static int ans = 0; public static void kills(int v, int p) { if (v == p) kills(tree.get(v).get(0), v); if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) kills(to, v); if (tree.get(v).size() >= 3) killed.set(v, killed.get(v) + 1); return; } public static void goup(int v, int p) { if (v == p) { for (Integer to : tree.get(v)) if (dist.get(to) < dist.get(v)) goup(to, v); killed.set(v, 0); return; } if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) goup(to, v); if (tree.get(v).size() >= 3) { killed.set(v, killed.get(v) + 1); return; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); for (int i=0;i<NMAX; i++) { tree.add(new ArrayList<Integer>()); dist.add(0); used.add(false); killed.add(0); } int n,v; n = in.nextInt(); if (n <= 5) {System.out.print(1); return;} // Частный случай tree.get(1).add(0); // Корень тоже должен быть "развилкой" ArrayList<Integer> leaves = new ArrayList<Integer> (); for (int i = 1; i < n; i++) { v = in.nextInt(); tree.get(v).add(i+1); tree.get(i+1).add(v); //Заполнение графа в том виде, в котором его дают } for (int i = 1; i <= n; i++) { if (tree.get(i).size() == 1 || (i == 1 && tree.get(i).size() == 2)) leaves.add(i); //Запоминаем все листья } LinkedList<Integer> q = new LinkedList<>(); dist.set(1, 0); q.offer(1); used.set(1, true); while (!q.isEmpty()) { int qv = q.poll(); used.set(qv, true); for (Integer to : tree.get(qv)) //BFS заполняющий вектор dist { if (!used.get(to)) { q.offer(to); dist.set(to, dist.get(qv)+1); } } } for (Integer l : leaves) { kills(l, l); // Первый этап - запросы от каждого листа } int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = Math.max(maxdist, dist.get(i)); // Определение максимального "уровня" дерева int wentup = 1; while (wentup != 0) { wentup = 0; for (int l = maxdist; l > 0; l--) { for (int i = 2; i <= n; i++) { if (killed.get(i) == 1 && dist.get(i) == l) { goup(i, i); //Этап 2 - поднятие "недошедших" запросов wentup++; } } } } for (int i = 1; i <= n; i++) if (killed.get(i) >= 2) ans++; //Финальный подсчет "отравленных" развилок System.out.print(ans); } } |
Решение задачи
Поскольку в задаче речь идет о дереве, циклов в нем нет по определению. Значит, единственным способом для термита ходить «вечно» будет путь между двумя листами, в которых он сможет разворачиваться. Фактически, задача сводится к вопросу «Какое минимальное количество вершин в дереве нужно отравить, чтобы нельзя было добраться из любого листа в другой лист не пройдя через отравленные?».
Определим для этого $3$ типа вершин: лист, развилка и обычная вершина. Листом назовем вершину, у которой нет детей (всего $1$ связь с другой вершиной). Обычные вершины — те, у которых ровно $2$ связи (для нашего термита это пути вниз или вверх). Развилкой назовем вершину, у которой $3$ или больше связей с другими. Будем считать корень тоже развилкой, даже если у него всего $2$ связи, или листом, если одна. Через развилки можно ходить из одного листа в другой, либо «вверх» — в сторону корня.
$1$ — корень; $5,6,3$ — листья; $4$ — развилка; $2$ — обычная;
Первый этап
Очевидно, выгоднее всего «закрывать» развилки. А среди них — те, которые соединяют несколько листов напрямую. Пусть каждый лист отправляет «запрос» вверх по дереву на закрытие ближайшей к нему развилки. Когда «запрос» доходит до развилки, он тут же записывается на её счёт. Таким образом, в дереве выше вершина $4$ будет иметь $2$ запроса — от листов $5$ и $6$, а корень — $1$ запрос от листа $3$.
Теперь, просто считаем количество вершин с количеством запросов $\geqslant2$ и «закрываем» их.
Второй этап
Увы, первый этап не идеален и может «не донести» запросы в нужное место, т.к. некоторые развилки (а именно — соединяющие лист и другую развилку) могут остаться с одним запросом и не быть закрытыми. Если таких много, термит все еще может ходить между листами. Например, в таком дереве:
Дерево, в котором необходим второй этап
Вершина $2$ и корень получают по $1$ запросу и остаются открытыми, а у термита остается путь между листами $10$ и $6$.
Для предотвращения таких случаев, пробежимся по дереву «снизу вверх» — от самого нижнего уровня до верхнего и для каждой развилки, у которой ровно $1$ запрос, сместим его вверх аналогично первому этапу — до ближайшей развилки. Будем выполнять этот шаг, пока есть такие вершины (с $1$ запросом).
В итоге, все запросы «соединятся» в нужных развилках, значение в них станет $\geqslant2$ и эти развилки нужно будет тоже закрыть. Для дерева выше, будет закрыт корень.
Осталось посчитать кол-во закрытых.
Описание алгоритма
Дерево будем хранить в ArrayList<ArrayList<Integer>> tree . Количество запросов для вершины $i$ хранится в killed.get(i). Стандартный ArrayList used для поиска в ширину и dist- ArrayList расстояний от корня до вершин, которые и будут определяться с помощью BFS.
Функция kills предназначена для того, чтобы донести запрос от листа до развилки. Она рассматривает $3$ случая:
- v == p — текущая вершина совпадает с той, из которой пришли. Это крайний случай, говорящий о том, что мы только начали и находимся в листе. Тогда, идем в единственно возможном направлении — tree.get(v).get(0).
- tree.get(v).size() == 2 — вершина обычного типа, просто идем «вверх», выбирая из двух путей тот, что не совпадает с предыдущей вершиной.
- tree.get(v).size() >= 3 — попали в развилку. Увеличиваем ее значение killed.get(v) и выходим из рекурсии.
Функция goup отличается от kills лишь тем, что при v == p выбирает из всех направлений то, которое ближе к корню, используя dist.
Подготовка
Можно заметить, что для всех деревьев из $5$ или менее вершин ответ будет $1$. Проверим это сразу при вводе n. Далее, осторожно считываем дерево в tree (см. Входные данные). В следующем цикле, определяем листья и запоминаем их в ArrayList leaves. Нужно учесть то, что корень может быть листом, если у него всего $2$ связи — одна с деревом, а другая — искусственно созданная нами в $0$ вершину. Последний шаг — запустить поиск в ширину из корня, который заполнит ArrayList dist расстояниями от корня до вершин.
Первый этап
Просто запускаем kills (l, l) из каждого листа l для «отправки» запросов в ближайшие развилки.
Второй этап
Определяем максимальную «глубину» дерева — максимальное расстояние вершины от корня. Далее, для каждого уровня от самого нижнего до корня, при определении вершины со значением killed.get(i) == 1 запускаем goup (i, i), а в переменной wentup считаем количество таких случаев. Как только их не останется — while выйдет из цикла.
Наконец, осталось просто посчитать количество вершин, у которых значение
killed.get(i) >= 2.
Задача на e-olymp
Код решения на ideone
Засчитанное решение на e-olymp