Yenə ağaclar#12372

Yenə ağaclar

1 saniyə

256 meqabayt

Çox çətin

$1$ nöqtəsi kök olan $n$ nöqtədən ibarət bir kök ağacı verilir. Hər bir nöqtədə bir tam ədəd var.

Aşağıdakı rekursiv prosedurdan istifadə edərək bir $a$ massivi qururuq:

dfs(v):
    nöqtə v-dəki ədədi a massivinin sonuna yaz
    nöqtə v-nin uşaqlarının istənilən sırasını seç
    seçilmiş sıradakı hər bir uşaq u üçün:
        dfs(u)

İlk olaraq, $df s (1)$ çağırılır.

Qeyd edək ki, hər bir nöqtədə uşaqların sırası istənilən şəkildə seçilə bilər, buna görə də, bu sıralamadan asılı olaraq, $a$ massivi fərqli ola bilər.

Bir elementi $a_{i}$ a_i prefiks maksimumu adlandıracağıq, əgər o, massivdəki bütün əvvəlki elementlərdən qat-qat böyükdür. Massivin ilk elementi də prefiks maksimumu hesab olunur.

$a$ massivində mümkün olan maksimum prefiks maksimumlarının sayını tapmaq lazımdır.

Giriş

İlk sətir ağacdakı nöqtələrin sayı $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5) — nöqtələrin sayıdır.

İkinci sətir $a$ massivini $(1 \leq a_{i} \leq 1 0^{9})$ (1 \le a_i \le 10^9) — nöqtələrdə yazılmış dəyərləri ehtiva edir.

Sonrakı $n - 1$ n-1 sətirdə iki ədəd $u$ və $v$ $(1 \leq u, v \leq n)$ (1 \le u, v \le n) verilir — ağacdakı kənarlar.

Çıxış

Tək bir ədəd çıxarın — $a$ massivində mümkün olan maksimum prefiks maksimumlarının sayı.

Nümunələr

Nümunə 1

Qeyd

İlk test nümunəsində aşağıdakı ağacımız var.

Ən əlverişli gedişi seçdikdən sonra aşağıdakı $[5, 2, 3, 6, 8, 7, 9]$ [5, 2, 3, 6, 8, 7, 9] massivini əldə edəcəyik.

Bu massiv üçün prefiks maksimumları $[5, 6, 8, 9]$ [5, 6, 8, 9] olacaq.

Bal hesablama

Alt tapşırıq $1$ ( $10$ xal): $(n \leq 10)$ (n \le 10)
Alt tapşırıq $2$ ( $20$ xal): $(a_{i} \leq 10)$ (a_i \le 10)
Alt tapşırıq $3$ ( $30$ xal): $(v = u - 1)$ (v = u-1)
Alt tapşırıq $4$ ( $30$ xal): $(u = 1)$ (u = 1)
Alt tapşırıq $5$ ( $40$ xal): $(n \leq 100)$ (n \le 100)
Alt tapşırıq $6$ ( $50$ xal): $(n \leq 500)$ (n \le 500)
Alt tapşırıq $7$ ( $70$ xal): $(n \leq 2000)$ (n \le 2000)
Alt tapşırıq $8$ ( $80$ xal): $(n \leq 75000)$ (n \le 75000)
Alt tapşırıq $9$ ( $170$ xal): Əlavə məhdudiyyət yoxdur