Опитування приладів#2001
Є пристроїв, кожен з яких потенційно з'єднаний кабелями з кількома підпорядкованими пристроями. Усі пристрої мають унікальні номери від до та утворюють дерево, коренем якого є пристрій номер .
Система обробляє запити таким чином: кореневий пристрій одночасно надсилає запит усім своїм безпосереднім підпорядкованим пристроям. Кожен підпорядкований пристрій пересилає запит далі своїм підпорядкованим, і цей процес триває по всьому дереву.
Кожен пристрій має певний час обробки даних, позначений як T_i мілісекунд.
Обробка даних кожним пристроєм відбувається так:
Якщо пристрій не має підпорядкованих, він через T_i мілісекунд повертає свій статус пристрою, від якого отримав запит.
Інакше він починає обробку, щойно отримує дані принаймні від % своїх безпосередніх підпорядкованих, і повертає результат через T_i мілісекунд.
Визначте максимальне значення , за якого весь процес виконання запиту завершиться за час, що не перевищує мілісекунд.
Запит вважається виконаним, коли кореневий пристрій отримав усю необхідну інформацію. Час передачі інформації між пристроями є незначним, а час обробки самого кореневого пристрою не враховується.
У першому рядку задано два цілі числа: (1 \leq N \leq 10000) і (0 \leq T \leq 10^6).
У наступних (N-1) рядках наведено опис пристроїв з номерами від до . Кожен рядок містить два цілі числа: P_i (1 \leq P_i \leq N) і T_i (0 \leq T_i \leq 100). Тут P_i — номер батьківського пристрою, тобто пристрій є підпорядкованим для пристрою P_i.
Виведіть максимальний відсоток з точністю принаймні знаки після коми.
Приклад 1