D. Давтагдахгүй органик нийлмэлүүд

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $n$ оройтой ($1$-c $n$ хүртэл дугаарлагдсан) $T$ мод өгөгдсөн ба орой бүртээ үсэгтэй. Модны үндэс нь $1$ дугаартай орой байна.

$v$ оройн зарим дэд мод $T_{v}$-г харцгаая. $v$ оройгоос эхэлж $T_{v}$-н нэг оройд дуусах ($v$ орой өөрөө байж болно) энгийн зам бүрийн дагуух тэмдэгт мөрийг унших боломжтой. Энэ замаар уншиж болох ялгаатай тэмдэгт мөрүүдийн тоог гэж тэмдэглэцгээе.

Мөн $v$ орой бүрт ноогдсон $c_{v}$ тоо байгаа. Бид утга нь хамгийн их байх оройнуудыг сонирхож байна.

Та хоёр үзүүлэлтийг тооцоолох ёстой: хамгийн их утгыг олох ба утгатай $v$ оройнуудын тоо.

Оролт

Оролтын эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 300 000$) байх ба модны оройн тоо.

Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоон утга $c_{i}$ ($0 ≤ c_{i} ≤ 10^{9}$) байна.

Гурав дахь мөрөнд $n$ ширхэг Англи цагаан толгойн жижиг үсгээс бүрдэх $s$ тэмдэгт мөр байх ба энэ тэмдэгт мөрийн $i$-р тэмдэг нь $i$ оройн үсэг байна.

Дараагийн $n - 1$ мөрөнд $T$ модыг тодорхойлно. Мөр бүрт зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $u$ ба $v$ ($1 ≤ u, v ≤ n$) байх ба $u$ ба $v$ оройн хоорондох ирмэгийг тодорхойлно.

Энэ нь оролт модыг тодорхойлно гэсэн үг.

Гаралт

Хоёр мөр хэвлэнэ.

Эхний мөрөнд бүх $1 ≤ i ≤ n$ дээр -г хэвлэ.

Хоёр дахь мөрөнд байх $v$ оройнуудын тоог хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
10
1 2 7 20 20 30 40 50 50 50
cacabbcddd
1 2
6 8
7 2
6 2
5 4
5 9
3 10
2 5
2 3
Гаралт
51
3
Оролт
6
0 2 4 1 1 1
raaaba
1 2
2 3
2 4
2 5
3 6
Гаралт
6
2

Тэмдэглэл

Эхний жишээн дээр мод дараах байдалтай харагдана:

Бие даасан оройнуудаас тэмдэгт мөрүүдийн бүрдэл нь:

Эцэст нь -н утгууд нь:

Хоёр дахь жишээн дээр -н утгууд нь $(5, 4, 2, 1, 1, 1)$. $T_{2}$-т уншигдаж байгаа ялгаатай тэмдэгт мөрүүд нь ;

нь $3$ эсвэл $4$ оройгоос доошоо уншигдаж чадна.

Сэтгэгдлүүдийг ачааллаж байна...