Ağacdakı inversiyalar#13094

Ağacdakı inversiyalar

3 saniyə

256 meqabayt

Sizə $1$ -dən $n$ -ə qədər nömrələnmiş $n$ təpədən ibarət ağac verilmişdir. Ağacın kökü $1$ nömrəli təpədir.

Hər bir $i$ təpəsində $p_{i}$ p_i ədədi yazılmışdır. Bütün ədədlər müxtəlifdir və $1$ -dən $n$ -ə qədər ədədlərin permutasiyasını təşkil edir.

Aşağıdakı hər iki şərti ödəyən $(u, v)$ təpələr cütü inversiya adlanır:

$u$ təpəsi $v$ təpəsinin ciddi əcdadıdır, yəni $u \neq = v$ u \ne v və $u$ kökdən $v$ təpəsinə gedən yol üzərində yerləşir.
$p_{u} > p_{v}$ p_u > p_v.

Ən çox bir əməliyyat yerinə yetirmək olar: ağacın istənilən kənarını seçib onun uclarındakı təpələrdə yazılmış ədədlərin yerlərini dəyişmək. Ağacın quruluşu dəyişmir.

Ən çox bir əməliyyatdan sonra əldə edilə bilən inversiyaların maksimum sayını tapın.

Giriş

Birinci sətirdə ağacın təpələrinin sayını bildirən $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \leq n \leq 2 \cdot 10^5) tam ədədi verilir.

İkinci sətirdə $n$ tam ədəd $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) — təpələrin üzərindəki ədədlər verilir. Bütün ədədlərin müxtəlif olduğuna zəmanət verilir.

Növbəti $n - 1$ n-1 sətrin hər birində ağacın bir kənarını göstərən iki tam ədəd $u$ və $v$ ( $1 \leq u, v \leq n$ 1 \leq u,v \leq n, $u \neq = v$ u \ne v) verilir.

Verilən qrafın ağac olduğuna zəmanət verilir.

Çıxış

Bir tam ədəd — inversiyaların mümkün olan maksimum sayını çap edin.

Nümunələr

Nümunə 1

Nümunə 2

Nümunə 3

Qeyd

Birinci nümunədə ağac yalnız bir təpədən ibarətdir. İnversiya yoxdur və heç bir əməliyyat yerinə yetirmək mümkün deyil. Cavab $0$ -dır.

İkinci nümunədə $1$ və $2$ nömrəli təpələrdəki ədədlərin yerlərini dəyişmək olar. Bundan sonra $1$ nömrəli təpədə $5$ , digər dörd təpədə isə daha kiçik ədədlər olacaq. $1$ nömrəli təpə digər dörd təpənin hər birinin əcdadı olduğuna görə $4$ inversiya alınır. Bundan çox inversiya əldə etmək mümkün deyil.

Üçüncü nümunədə təpələr $1$ – $2$ – $3$ – $4$ yolunu təşkil edir və onların üzərindəki ədədlər $4, 3, 2, 1$ 4,3,2,1-dir. Müxtəlif təpələrdən ibarət hər bir cüt inversiyadır, buna görə onların sayı $6$ -dır. Dörd təpə üçün mümkün olan maksimum say budur və əməliyyata ehtiyac yoxdur.

Bal hesablama

$20$ bal — $1 \leq n \leq 10$ 1 \leq n \leq 10.
$30$ bal — ağacın mərkəzi $1$ nömrəli təpə olan ulduz şəklində olması.
$40$ bal — ağacın uclarından biri $1$ nömrəli təpə olan sadə yol olması.
$90$ bal — $1 \leq n \leq 3000$ 1 \leq n \leq 3000.
$120$ bal — əlavə məhdudiyyət yoxdur.