Дерево на прямій
Обмеження: 2 сек., 256 МіБ
Зеник має дерево з \(n\) вершин, пронумерованих від 1 до \(n\) включно.
Марічка має перестановку \(p\) цілих чисел від 1 до \(n\) включно.
Одного дня їх зацікавило таке питання. Скільки є проміжків \([l, r] (1 \le l \le r \le n)\) таких, що вершини \(p_l, p_{l+1}, \ldots, p_r\) утворюють зв’язний підграф Зеникового дерева?
Допоможіть їм і знайдіть відповідь.
Вхідні дані
Перший рядок містить ціле число \(n\).
Другий рядок містить \(n\) цілих чисел \(p_i\) — Маріччину перестановку.
Наступні \(n-1\) рядків описують ребра Зеникового дерева. Кожен рядок містить пару вершин, які з’єднує відповідне ребро.
Вихідні дані
У єдиному рядку виведіть ціле число — відповідь на задачу.
Обмеження
\(1 \le n \le 10^5\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 1 5 3 2 4 3 5 5 1 1 4 2 1 | 10 |
Джерело: The Grand Contest 2019
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|