Козак Вус у Деревляндії#31

Козак Вус у Деревляндії (Editorial)

Спочатку розберемося, скільки трас потрібно за фіксованої столиці.

Підвісимо дерево за обрану столицю. Кожна траса — це шлях зі столиці вниз, і разом вони мають покрити всі вершини. Кожен лист (вершина без нащадків) може бути лише кінцем траси, причому власної: жодна траса не проходить через лист далі. Тому трас потрібно щонайменше стільки, скільки листків. З іншого боку, цієї кількості й вистачає — достатньо взяти по одному шляху від кореня до кожного листка, і разом вони покриють усе дерево.

Отже, за фіксованого кореня відповідь дорівнює кількості листків підвішеного дерева.

Тепер оберемо корінь якнайкраще. Нехай — кількість вершин степеня у вихідному (непідвішеному) дереві. Якщо зробити коренем внутрішню вершину, всі таких вершин залишаться листками. Якщо ж зробити коренем саме вершину степеня , вона перестає бути листком, і залишається рівно L - 1 листок. Це найкраще з можливого, тому мінімальна кількість трас дорівнює

L - 1.

Оскільки будь-яка вершина степеня дає однаковий результат, а за умови потрібен найменший номер, виводимо найменший номер серед вершин степеня . У дереві з n \ge 2 вершин така вершина завжди існує.

Реалізація проста: зчитуємо ребра, рахуємо степені, знаходимо найменшу вершину зі степенем і кількість таких вершин. Складність — , обходити дерево навіть не обов'язково.

Перевірте на прикладі «зірки»: центр і три промені дають L = 3, тобто дві траси, — і справді, з листка можна дійти до центра й далі до двох інших листків двома шляхами.