Інверсії в дереві#13094

Інверсії в дереві

3 секунди

256 мегабайтів

Дано дерево з $n$ вершинами, пронумерованими від $1$ до $n$ . Коренем дерева є вершина $1$ .

У кожній вершині $i$ записано число $p_{i}$ p_i. Усі ці числа різні та утворюють перестановку чисел від $1$ до $n$ .

Назвемо інверсією пару вершин $(u, v)$ , для якої виконуються обидві умови:

Вершина $u$ є строгим предком вершини $v$ , тобто $u \neq = v$ u \ne v і вершина $u$ лежить на шляху від кореня до вершини $v$ .
$p_{u} > p_{v}$ p_u > p_v.

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

Знайдіть найбільшу можливу кількість інверсій після виконання не більше однієї операції.

Вхідні дані

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

У другому рядку задано $n$ цілих чисел $p_{1}, p_{2}, \dots, p_{n}$ p_1,p_2,\ldots,p_n ( $1 \leq p_{i} \leq n$ 1 \leq p_i \leq n) — мітки вершин. Гарантується, що всі числа різні.

У кожному з наступних $n - 1$ n-1 рядків задано два цілі числа $u$ та $v$ ( $1 \leq u, v \leq n$ 1 \leq u,v \leq n, $u \neq = v$ u \ne v), що означають наявність ребра між вершинами $u$ та $v$ .

Гарантується, що заданий граф є деревом.

Вихідні дані

Виведіть одне ціле число — найбільшу можливу кількість інверсій.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі дерево складається з однієї вершини. Інверсій немає, а виконати операцію неможливо. Тому відповідь дорівнює $0$ .

У другому прикладі можна поміняти місцями числа у вершинах $1$ та $2$ . Після цього у вершині $1$ буде записано $5$ , а в усіх інших вершинах — менші числа. Оскільки вершина $1$ є предком кожної з решти чотирьох вершин, отримаємо $4$ інверсії. Більшої кількості досягти неможливо.

У третьому прикладі вершини утворюють шлях $1$ – $2$ – $3$ – $4$ , а записані в них числа дорівнюють $4, 3, 2, 1$ 4,3,2,1. Кожна пара різних вершин є інверсією, тому їхня кількість дорівнює $6$ . Це найбільша можлива кількість для чотирьох вершин, тож операцію виконувати не потрібно.

Оцінювання

$20$ балів — $1 \leq n \leq 10$ 1 \leq n \leq 10.
$30$ балів — дерево є зіркою з центром у вершині $1$ .
$40$ балів — дерево є простим шляхом, одним із кінців якого є вершина $1$ .
$90$ балів — $1 \leq n \leq 3000$ 1 \leq n \leq 3000.
$120$ балів — без додаткових обмежень.