Ağaçta ters çiftler#13094

Ağaçta ters çiftler

3 saniye

256 megabayt

Size $1$ 'den $n$ 'e kadar numaralandırılmış $n$ düğümden oluşan bir ağaç veriliyor. Ağacın kökü $1$ numaralı düğümdür.

Her $i$ düğümünde $p_{i}$ p_i etiketi yazılıdır. Tüm etiketler farklıdır ve $1$ 'den $n$ 'e kadar olan tam sayıların bir permütasyonunu oluşturur.

Aşağıdaki iki koşulu da sağlayan $(u, v)$ düğüm çiftine ters çift (inversiyon) denir:

$u$ düğümü $v$ düğümünün öz atasıdır, yani $u \neq = v$ u \ne v ve $u$ düğümü kökten $v$ düğümüne giden yol üzerinde bulunur.
$p_{u} > p_{v}$ p_u > p_v.

En fazla bir işlem yapabilirsiniz: herhangi bir kenarı seçip uçlarındaki etiketlerin yerlerini değiştirmek. Ağacın yapısı değişmez.

En fazla bir işlem yaptıktan sonra elde edilebilecek en büyük ters çift sayısını bulun.

Giriş

Birinci satırda ağacın düğüm sayısını belirten bir $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \leq n \leq 2 \cdot 10^5) tam sayısı verilir.

İkinci satırda $n$ tam sayı $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) — etiketler verilir. Bu sayıların tamamının farklı olduğu garanti edilir.

Sonraki $n - 1$ n-1 satırın her birinde ağacın bir kenarını belirten iki tam sayı $u$ ve $v$ ( $1 \leq u, v \leq n$ 1 \leq u,v \leq n, $u \neq = v$ u \ne v) verilir.

Verilen çizgenin bir ağaç olduğu garanti edilir.

Çıktı

Tek bir tam sayı — mümkün olan en büyük ters çift sayısını yazdırın.

Örnekler

Örnek 1

Örnek 2

Örnek 3

Not

Birinci örnekte ağaç tek bir düğümden oluşur. Hiç ters çift yoktur ve herhangi bir işlem yapmak mümkün değildir. Bu nedenle cevap $0$ 'dır.

İkinci örnekte $1$ ve $2$ numaralı düğümlerdeki etiketlerin yerleri değiştirilir. Bundan sonra $1$ numaralı düğümde $5$ bulunur ve diğer dört düğümde daha küçük etiketler bulunur. $1$ numaralı düğüm bunların hepsinin atası olduğundan $4$ ters çift elde edilir. Daha büyük bir değer elde etmek mümkün değildir.

Üçüncü örnekte düğümler $1$ – $2$ – $3$ – $4$ yolunu oluşturur ve etiketleri $4, 3, 2, 1$ 4,3,2,1'dir. Birbirinden farklı her düğüm çifti bir ters çifttir, dolayısıyla toplam $6$ ters çift vardır. Bu, dört düğüm için zaten mümkün olan en büyük değerdir, bu yüzden herhangi bir işlem yapmaya gerek yoktur.

Puanlama

$20$ puan — $1 \leq n \leq 10$ 1 \leq n \leq 10.
$30$ puan — ağaç, merkezi $1$ numaralı düğüm olan bir yıldızdır.
$40$ puan — ağaç, uçlarından biri $1$ numaralı düğüm olan basit bir yoldur.
$90$ puan — $1 \leq n \leq 3000$ 1 \leq n \leq 3000.
$120$ puan — ek kısıt yoktur.