Дерево з годинником#10122

Дерево з годинником

1 секунда
128 мегабайтів
Дуже легка

Новий амбар Фермера Джона складається з кімнат, пронумерованих від до , і n - 1 коридорів. Кожен коридор з'єднує пару кімнат так, що можна дістатися з будь-якої кімнати до будь-якої іншої через серію коридорів.

У кожній кімнаті амбару є круглий годинник на стіні зі стандартним розташуванням цифр від до . Проте на цих годинниках є лише одна стрілка, яка завжди вказує точно на одне з цих чисел (вона ніколи не зупиняється між двома числами).

Корова Бессі хоче синхронізувати всі годинники в амбарі, щоб вони показували число . Але через своє коров'яче мислення, кожного разу, коли вона заходить у кімнату, вона переміщує стрілку вперед на одну позицію. Наприклад, якщо стрілка показувала на , Бессі переводить її на . Якщо годинник вказував на , вона переводить стрілку на . Якщо Бессі заходить у кімнату кілька разів, вона переміщує стрілку при кожному вході.

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

Вхідні дані

Перший рядок містить число n~(2 \le n \le 2500). Наступний рядок містить цілих чисел, кожне в інтервалі , що вказують початкові положення стрілок у кожній кімнаті. Кожен з наступних n - 1 рядків описує коридор двома цілими числами і , кожне в інтервалі , які задають номери кімнат, з'єднаних цим коридором.

Вихідні дані

Виведіть кількість кімнат, з яких Бессі може почати свій шлях, щоб встановити всі годинники на .

Приклади

У цьому прикладі Бессі може встановити всі годинники на , тільки якщо вона почне свій шлях у кімнаті (і далі, наприклад, перейшовши в кімнату 1, 2, 3, 2 і, нарешті, ).

Приклад 1

Loading
Loading