І знову дерева#12372

І знову дерева

1 секунда

256 мегабайтів

Дуже складна

Дано кореневе дерево з $n$ вершин, де коренем є вершина $1$ . У кожній вершині записано ціле число.

Ми будуємо масив $a$ за допомогою такої рекурсивної процедури:

dfs(v):
    записати число у вершині v в кінець масиву a
    вибрати довільний порядок синів вершини v
    для кожного сина u у вибраному порядку:
        dfs(u)

Спочатку викликається $df s (1)$ .

Зауважимо, що порядок синів у кожній вершині можна вибирати довільно, тому залежно від цього масив $a$ може бути різним.

Назвемо елемент $a_{i}$ a_i префіксним максимумом, якщо він строго більший за всі попередні елементи масиву. Перший елемент масиву також вважається префіксним максимумом.

Необхідно знайти максимальну можливу кількість префіксних максимумів у масиві $a$ .

Вхідні дані

В першому рядку задано число $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5) — кількість вершин в дереві.

В другому рядку задано масив $a$ $(1 \leq a_{i} \leq 1 0^{9})$ (1 \le a_i \le 10^9) — значення які записані в вершинах.

В наступних $n - 1$ n-1 рядках задано два числа, $u$ та $v$ $(1 \leq u, v \leq n)$ (1 \le u , v \le n) — ребра в дереві

Вихідні дані

Вивести одне число — максимальну можливу кількість префіксних максимумів у масиві $a$ .

Приклади

Приклад 1

Примітка

В першому тестовому випадку маємо таке дерево.

Після вибору найвигіднішого обходу будемо мати наступний масив $[5, 2, 3, 6, 8, 7, 9]$ [5 , 2 , 3 , 6 , 8 , 7 , 9].

Префіксними максимумами для цього масиву будуть $[5, 6, 8, 9]$ [5,6,8,9].

Оцінювання

Підзадача $1$ ( $10$ балів) : $(n \leq 10)$ (n \le 10)
Підзадача $2$ ( $20$ балів) : $(a_{i} \leq 10)$ (a_i \le 10)
Підзадача $3$ ( $30$ балів) : $(v = u - 1)$ (v = u-1)
Підзадача $4$ ( $30$ балів) : $(u = 1)$ (u = 1)
Підзадача $5$ ( $40$ балів) : $(n \leq 100)$ (n \le 100)
Підзадача $6$ ( $50$ балів) : $(n \leq 500)$ (n \le 500)
Підзадача $7$ ( $70$ балів) : $(n \leq 2000)$ (n \le 2000)
Підзадача $8$ ( $80$ балів) : $(n \leq 75000)$ (n \le 75000)
Підзадача $9$ ( $170$ балів) : Без додаткових обмежень