Розробка вакцини
Обмеження: 2 сек., 256 МіБ
Марічка та Зеник — видатні науковці. Уже дуже довго вони розробляють вакцину, що повністю подолає реп’яховірус.
Реп’яховірус складається з молекул та зв’язків між ними. Молекули пронумеровані від 1 до \(n\). Марічка з Зеником з’ясували, що молекули реп’яховірусу формують дерево (зв’язний граф без циклів) з коренем у молекулі 1.
Молекула називається слабкою, якщо вона зв’язана лише з однією іншою молекулою.
Реп’яховірус постійно розвивається: у ньому з’являються нові слабкі молекули, що приєднуються до наявних молекул.
Марічка та Зеник просять вас написати програму, що прискорить розробку вакцини.
Програма повинна обробляти два типи запитів:
1\(v\) — з’являється нова молекула з номером \(m + 1\), що приєднана до молекули \(v\) (тут \(m\) — кількість молекул перед виконанням запиту).2\(v\) — знайти довжину найкоротшого шляху (необов’язково простого), що починається в молекулі \(v\) та проходить через усі слабкі молекули в піддереві цієї молекули. Довжиною шляху називається кількість ребер (зв’язків) у цьому шляху.
Вхідні дані
У першому рядку задано ціле число \(n\) — початкову кількість молекул у реп’яховірусі.
Кожен з наступних \(n-1\) рядків містить пару цілих чисел — \(a_i\) та \(b_i\), яка означає, що існує зв’язок між відповідними молекулами.
Наступний рядок містить ціле число \(q\) — кількість запитів.
У наступних \(q\) рядках задано
запити, по одному на рядок. Кожен запит має вигляд \(t\) \(v\),
де \(t\) — тип запиту (1
або 2), а \(v\) — номер
молекули. Така молекула гарантовано існує на момент запиту.
Вихідні дані
Для кожного запиту другого типу виведіть рядок, що містить ціле число — відповідь на цей запит.
Обмеження
\(1 \le n \le 2 \cdot 10^5\),
\(1 \le q \le 2 \cdot 10^5\),
є щонайменше один запит другого типу.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 10 1 2 2 3 3 5 3 4 2 6 6 7 1 8 8 9 8 10 5 2 2 2 8 1 8 2 8 2 10 | 8 3 5 0 |
Примітки
Для першого запиту оптимальний шлях — \(2\to3\to4\to3\to5\to3\to2\to6\to7\),
Для другого — \(8\to9\to8\to10\).
Для четвертого — \(8\to9\to8\to10\to8\to11\).
Для п’ятого — \(10\).
Надіслати розв'язок
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|
Розробка вакцини - Розбір
Яка довжина найкоротшого шляху, що починається в корені дерева проходить через усі листки дерева, а тоді повертається у корінь? Легко бачити, що такий шлях проходить по кожному ребру рівно 2 рази, а тому його довжина — \(2n - 2\), де \(n\) — кількість вершин у дереві.
Як змінюється ця довжина якщо нам не потрібно повертатися в корінь після відвідування останнього листка? Нехай \(D_v\) — відстань від кореня до вершини \(v\) (ми також називатимемо цю величину глибиною вершини \(v\)). Зрозуміло, що закінчивши у листку \(x\), ми економимо рівно \(D_x\) ребер. Отже, вигідно закінчити наш маршрут у вершині, для якої \(D_v\) максимальне.
Таким чином, щоб відповісти на запит другого типу нам потрібно знати кількість вершин у піддереві, а також глибину найглибшого листка. Якби не було запитів першого типу, то було б достатньо обчислити ці значення для усіх вершин за допомогою пошуку в глибину. Як же бути з запитами першого типу? Від задачі з додаванням вершин перейдемо до задачі з "увімкненням" вершин. Розглянемо дерево, що вийде після виконання усіх запитів першого типу (ми називатимемо його фінальним деревом). Тепер вважатимемо, що кожна вершина в цьому дереві може бути або увімкненою, або ні. Коли відбувається запит першого типу, то ми вмикаємо відповідну вершину. Для запиту другого типу нам потрібно знайти кількість увімкнених вершин у піддереві та максимальну глибину серед увімкнених вершин у піддереві.
Побудуємо Ейлеровий обхід фінального дерева: випишемо усі вершини дерева в порядку обходу в глибину. Кожному піддереву відповідає деякий неперервний відрізок в цьому обході. Це дозволяє перетворити запити на піддереві у запити на відрізку. Отож, тепер нам потрібна структура даних, що ефективно виконує такі операції:
змінити значення елемента (щоб увімкнути вершину)
знайти суму на відрізку (щоб знайти кількість вершин у піддереві)
знайти максимальний елемент на відрізку (щоб знайти найглибшого листка)
Одна з таких структур — дерево відрізків. Вона може виконувати кожен з цих запитів з логарифмічною складністю.
Загальна складність — \(O(n + q \log(n))\).
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|