4 тур - з 03.12 по 10.12.2018

точка входу для відправлення розв'язків
http://134.249.159.199//cgi-bin/new-client?contest_id=65

(скачать)

Задача A. Новорічні забави (100 балів)

Обмеження по часу:      1 секунда

Обмеження по пам'яті: 512 мегабайт

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

Дерево фейерверків містить одну або кілька вершин. Одна з вершин виділена та називається коренем, для кожної з решти вершин тільки одна інша вершина є батьківською. При цьому від будь-якої вершини можна дістатись до кореня, послідовно рухаючись від вершини до її батьківської вершини. Вершина, яка не є батьківською для жодної іншої вершини, - називається листом. Якщо вершина х є батьківською для вершини y, тоді вершина у називається нащадком вершини х. Кажуть, що вершина та її батьківська вершина з'єднані ребром.

На рис.1 показано приклад дерева з коренем в вершині 1. Батьківською вершиною для вершин 2 та 3 є вершина 1, батьківською вершиною для вершини 4 є вершин 2. Вершини 2 та 3 - нащадки вершини 1, а вершина 4 - нащадок вершини 2. Листами є вершини 3 та 4.

Рис.1 Приклад дерева з коренем в вершині 1, листами 3 та 4.

Фейерверк задається своїм базовим деревом Т та потужністю m. Фейерверк є деревом, яке отримується в результаті піднесення дерева Т до степеня m. Операція піднесення дерева до степеня побудована наступним чином. Якщо m=1, тоді результат Т¹ - саме дерево. Т. Для m>1 розглянемо дерево Т^m-1. Виконаємо наступну операцію: для кожного листа х дерева Т^m-1 створимо копію дерева Т та призначимо лист х батьківською вершиною для кореня відповідної копії. Отримане дерево буде деревом Т^m.

На рис. 2 показано дерево (рис.1), в степенях 1, 2 та 3.

Рис.2. Приклад піднесення дерева до степенів 1,2 та 3.

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

Щоб оцінити красу фейерверку, необхідно обчислити, яку максимальну кількість вершин може містити шлях в дереві, яким подається фейерверк. На рис.3 наведено шлях в дереві Т², який містить максимальну кількість вершин. Отже, краса фейерверку з базовим дерево Т та потужністю 2 дорівнює 10.

Рис. 3. Шлях в дереві Т², який містить максимальну кількість вершин.

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

Формат вхідних даних

Перший рядок вхідних даних містить два натуральних числа n та m - кількість вершин в базовому дереві фейерверку Т та його потужність (3≤n≤200 000, 1≤m≤200 000).

Другий рядок описує дерево Т та містить (n-1) цілих чисел: p₁, p₂, ..., p_n - номера батьківських вершин 2, 3, ..., n, відповідно (1≤p_i≤i-1).

Формат вихідних даних

Необхідно вивести одне ціле число - красу фейерверку, який представлений деревом Т^m.

Приклад вхідних та вихідних даних

Задача B. Приватизація доріг у Фестляндії (100 балів)

Обмеження по часу:      3 секунди

Обмеження по пам'яті: 256 мегабайт

В країні Фестляндії не тільки святкують, але й працюють.

Відомо, що у Фестляндії є n міст та m двосторонніх доріг. Кожна дорога з'єднує два різних міста.

Нещодавно уряд Фестляндії приймає жорстке рішення про передачу права власності на дороги приватним компаніям. В цілому є100500 приватних компаній в Фестляндії, які пронумеровані цілими числами від 1 до 100500. Після приватизації кожна дорога повинна належати хоча б одній компанії.

Антимонопольний комітет вимагає, щоб після приватизації кожна компанія могла володіти не більше, ніж двома дорогами. Урбаністи Фестляндії також висловили свою думку: кожне місто повинно бути приєднаним до доріг, якими володіють не більше, ніж k компаній.

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

Формат вхідних даних

Вхідний файл містить один або декілька тестів. Перший рядок містить ціле число t (1 ≤  t ≤ 300) - кількість тестів на вході. Розв'язуйте тести окремо, тести повністю незалежні і не впливають один на одного.

Наступні рядки описують тести. Кожен тест починається з рядка, що складається з трьох цілих чисел, розділених пробілом,  n, m, k (2 ≤ n ≤ 600, 1 ≤ m ≤ 600, 1 ≤ k ≤ n - 1) - кількість міст, кількість доріг і максимальна кількість доріг, прилеглих до міста.

Кожен з наступних m рядків містить пару цілих чисел, розділених пробілом a_i, b_i (1 ≤ a_i, b_i ≤ n; a_i ≠ b_i) Це означає, що i-та дорога з'єднує міста a_i та b_i. Всі дороги є двосторонніми. Між парою міст є не більше однієї дороги.

Загальне значення n для всіх тестів не перевищує 600. Загальне значення m для всіх тестів не перевищує 600.

Формат вихідних даних

Вивести n рядків. Кожен і-ий рядок повинен містити відповідь для і-го тесту: послідовність цілих чисел с₁, c₂, ... , с_m ,розділених пробілом, де с_і (1 ≤ с_і ≤ 100500) - це компанія, яка володіє і-ою дорогою у вашому плані. Якщо є декілька розв'язків,  - виведіть будь-який з них. Якщо розв'язок для теста не знайдено, виведіть с₁,=c₂=... =с_m = 0.

Приклад вхідних та вихідних даних