Охрана выставки
Выставка занимает n залов, соединённых проходами так, что из любого зала в любой можно попасть ровно одним путём без повторов: залы и проходы образуют дерево. Охранник, стоящий в зале, видит все проходы, которые из этого зала выходят. Сколько охранников нужно как минимум, чтобы был виден каждый проход?
Деревья в тестах бывают очень глубокими — вплоть до одной длинной анфилады из двухсот тысяч залов.
Вход
В первой строке — n (1 ≤ n ≤ 200 000). Дальше n − 1 строк по два числа a и b (1 ≤ a, b ≤ n): проход между залами a и b.
Выход
Одно число — наименьшее число охранников.
Примеры
Пример 1
7 1 2 2 3 1 4 4 5 1 6 6 7
3
Пример 2
5 1 2 2 3 3 4 4 5
2
Ограничения
- Время · Python
- 2000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Поставить охранника туда, где больше всего проходов, — разумно, но в первом примере это даёт четыре охранника, а хватает трёх. Подвесьте дерево за любой зал. Что нужно знать о поддереве зала, чтобы решить задачу для его родителя?
2Подсказка 2
Для поддерева важно одно: стоит ли охранник в его корне. От этого зависит, нужен ли охранник у родителя, чтобы был виден проход между ними.
3Идея
Для каждого зала v два числа: guard[v] — сколько нужно охранников в его поддереве, если в самом v охранник есть, и free[v] — если нет. Если в v охранник есть, проходы к детям уже видны, и каждому ребёнку берём лучшее из двух: guard[v] = 1 + Σ min(guard[c], free[c]). Если нет — каждый проход к ребёнку должен быть виден со стороны ребёнка: free[v] = Σ guard[c]. Ответ — min(guard, free) у корня. Это динамика на деревьях.
4Разбор
Дети должны быть посчитаны раньше родителя. Рекурсивный обход это обеспечивает, но в Python на анфиладе из двухсот тысяч залов он упрётся в предел глубины рекурсии, а поднятый предел — в размер стека. Надёжнее без рекурсии: обойти дерево в ширину от зала 1, запоминая родителей, и пройти полученный список задом наперёд — тогда каждый зал встречается после всех своих потомков и сразу отдаёт свои два числа родителю.
В первом примере у центрального зала три коридора по два зала. Охранник в центре видит три прохода, но в каждом коридоре остаётся по проходу, и нужны ещё три охранника — всего четыре. А три охранника в средних залах коридоров видят все шесть проходов. На дереве адресов этого сайта, где 8986 узлов, хватает 116 охранников.
4+Решение
5Сложность
O(n): каждый зал один раз попадает в обход и один раз отдаёт числа родителю. На произвольном графе эта задача — наименьшее вершинное покрытие — NP-трудна; на дереве её делает лёгкой то, что поддеревья друг с другом не связаны.
6Типичные ошибки
- Сначала самый людный зал. Не проходит первый пример: центр с тремя проходами кажется выгодным, но оставляет три непокрытых прохода в разных местах.
- Рекурсия в Python. На длинной анфиладе — RecursionError или падение из-за стека, даже если алгоритм верный.
- Одно число на зал. Без разделения «с охранником / без» родитель не узнает, виден ли проход к ребёнку.