Десантна операція
Обмеження: 3 сек., 256 МіБ
Українські війська продовжують активний контрнаступ! Наші десантники щодня планують нові атакувальні операції.
Зараз під контролем ворога знаходиться \(n\) сіл, які з’єднанні \((n-1)\)-ою дорогами довжиною 1 кілометр так, що з кожного села можна дістатися до будь-якого іншого (можливо через інші села). У \(i\)-тому селі є \(a_i\) окупантів. Село з номером один знаходиться найзахідніше, усі села, що безпосередньо з’єднані з ним, знаходяться трішки східніше, ті, що з’єднані з ними (окрім села з номером 1) ще східніше і так далі.
Десант розглядає \(q\) варіантів наступної атаки. \(і\)-й варіант передбачає висадку у селі з номером \(v_i\) та швидку нейтралізацію усіх противників у селах, що знаходяться на відстані не більшій ніж \(d_i\) кілометрів від місця висадки. Зауважте, що наш десант рухається лише вперед, а тому він нейтралізовує противників лише у селах, що знаходяться східніше від місця висадки. Допоможіть знайти точне число нейтралізованих противників для кожного з варіантів атаки.
Вхідні дані
У першому рядку задано два цілих числа \(n\) та \(q\) — кількість сіл та кількість варіантів атаки.
У другому рядку задано \(n\) цілих чисел \(a_i\) — кількість окупантів в \(і\)-тому селі.
У наступних \(n-1\) рядках задано по два цілих числа \(u_i\) та \(w_i\) — дороги між селами.
У наступних \(q\) рядках задано по два цілих числа \(v_i\) і \(d_i\) — місце висадки та максимальна відстань, на якій нейтралізовуватиме противників десант.
Вихідні дані
У \(q\) рядках виведіть по одному числу — кількості нейтралізованих противників для кожного з варіантів атаки.
Обмеження
\(1 \le n, q \le 10^{5}\),
\(1 \le a_i \le 10^{9}\),
\(1 \le u_i, w_i \le n\),
\(1 \le v_i, d_i \le n\).
Оцiнювання задачi складається iз наступних блокiв:
1 бал — приклад з умови,
4 бали — блок тестів у яких \(n, q\le 10^{3}\).
5 балів — блок тестів у яких \(d_i = n\).
15 балів — блок тестів без додаткових обмежень.
Бали за блок ви отримаєте, лише якщо дасте правильну вiдповiдь на всi тести з блоку.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
7 4 3 2 4 1 2 1 5 1 2 2 3 3 4 3 5 4 6 1 7 2 2 3 2 3 1 5 3 | 9 8 7 2 |
Примітки
відповідь на перший запит \(9\), бо десант нейтралізує ворогів у селах \(2,3,4,5\)
відповідь на другий запит \(8\), бо десант нейтралізує ворогів у селах \(3,4,5,6\)
відповідь на третій запит \(7\), бо десант нейтралізує ворогів у селах \(3,4,5\)
відповідь на четвертий запит \(2\), бо десант нейтралізує ворогів у селі \(5\)
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|