E. Урьдчилсан дарааллын шалгалт

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

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

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

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

Компьютерийн ухааны хичээлдээ зориулж Жэкоб бөмбөг болон мөчрөөр загвар мод байгуулсан ба $n$ зангилаатай ба мод хэлбэрийн дүрстэй. Жэкоб модон дахь $i$-р бөмбөгийг байгуулах гэж $a_{i}$ минут зарцуулсан.

Жэкобын багш түүний загварыг зарцуулсан хүч хөдөлмөрөөр нь үнэлэж дүн тавина. Гэсэн хэдий ч тэр үүнийг тодорхойлохын тулд модыг бүхлээр нь шалгах хангалттай цаг түүнд байхгүй; Жэкоб багшийгаа модны эхний $k$ нүдийг DFS-эрэмбэлэн огтлох аргаар шалгана гэдгийг мэдэж байгаа. Тэр Жэкобд эдгээр $k$ зангилаанаас олсон хамгийн бага $a_{i}$ утгатай тэнцүү дүн тавина.

Гэсэн ч Жэкобд загвараа дахин байгуулах хангалттай цаг байхгүй, тэр багшийнхаа эхлэх зангилаа буюу үндэс зангилааг сонгож чадна. Түүнээс гадна тэр зангилаа бүрийн хөршүүдийн жагсаалтыг хүссэнээрээ дахин байрлуулж чадна. Жэкобд энэ бие даалтан дээрээ авч чадах хамгийн их дүнгээ олоход туслана уу.

DFS-эрэмбэлэн огтлох нь үндэстэй модны зангилаануудыг эрэмбэлэх юм, эхлээд модны үндэс дээр дуудагддаг рекурсив DFS процедураар хийгддэг үйлдэл юм. Өгөгдсөн $v$ зангилаан дээр дуудагдсан үед процедур дараах зүйлсийг хийдэг:

  1. $v$-г хэвлэнэ.
  2. Дарааллын дагуу $v$ зангилааны хөршүүдийн жагсаалтанд эргэлдэх ба давталттайгаар нэг бүр дээр DFS процедурыг дууддаг. Хэрвээ та $u$ зангилаанаас шууд $v$ зангилааруу ирсэн бол $u$ зангилаан дээр DFS процедурыг дуудахгүй.

Оролт

Оролтын эхний мөрөнд хоёр эерэг бүхэл тоон утга $n$ ба $k$ ($2 ≤ n ≤ 200 000$, $1 ≤ k ≤ n$) байх ба Жэкобын модон дахь бөмбөгүүдийн тоо ба багшийн шалгах бөмбөгүүдийн тоо.

Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утга $a_{i}$ ($1 ≤ a_{i} ≤ 1 000 000$) байх ба Жэкоб $i$-р бөмбөгийг байгуулсан хугацаа.

Дараагийн $n - 1$ мөр бүрт хоёр бүхэл тоон утга $u_{i}$, $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$, $u_{i} ≠ v_{i}$) байх ба Жэкобын модон дахь $u_{i}$ болон $v_{i}$ бөмбөгүүдийн хоорондох холболтыг илэрхийлнэ.

Гаралт

Жэкоб модны зөв үндсийг сонгож, хөршийн жагсаалтыг шинэчлэснээр авч чадах хамгийн их дүнг илэрхийлэх нэг ширхэг бүхэл тоон утгыг хэвлэ.

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

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

Оролт
5 3
3 6 1 4 2
1 2
2 4
2 5
1 3
Гаралт
3
Оролт
4 2
1 5 5 5
1 2
1 3
1 4
Гаралт
1

Тэмдэглэл

Эхний жишээн дээр Жэкоб $2$ дугаартай зангилааг модны үндэсээр сонгох ба хөршүүдийг $4$, $1$, $5$ гэж дарааллуулна (бусад бүх зангилаа хамгийн ихдээ хоёр хөрштэй). Урьдчилсан дарааллаар огтолж гарахад $2$, $4$, $1$, $3$, $5$ байх ба эхний $3$ зангилааны хамгийн бага $a_{i}$ нь $3$ байна.

Хоёр дахь жишээн дээр дурын урьдчилсан дарааллаар огтолж гарах гаралтанд $1$ зангилаа заавал нэгдүгээр эсвэл хоёрдугаар зангилаа хэлбэрээр агуулагдана, ингээд Жэкоб $1$-с илүү дүн авч чадахгүй.

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