B. Их сургуулиудыг холбох

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

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

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

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

Трийлэнд бол ямар ч хотоос өөр дурын хотруу очиж болохуйц $n - 1$ хос чиглэлт замаар хоорондоо холбогдсон $n$ хоттой улс юм.

Трийлэндэд ялгаатай хотуудад байрласан $2k$ их сургууль байдаг.

Саяхан Ерөнхийлөгч их сургуулиудыг өндөр хурдны сүлжээгээр холбох тушаалд гарын үсэг зурсан. Боловсролын яамны сайд тушаалыг өөрийнхөөрөө ойлгож их сургууль бүрийг өөр нэгэнтэй нь кабелиар холбоход хангалттай гэж шийдсэн. Өнгөцхөндөө тушаал биелнэ.

Төсөв хамгийн их байх үүднээс сайд их сургуулиудыг нийт шаардлагатай кабелийн урт хамгийн их байхаар хосуудад хуваахаар шийдсэн. Өөрөөр хэлбэл $k$ хос бүхий их сургуулиудын хоорондох зай боломжит хамгийн их байх ёстой.

Сайдад нийт зайн хамгийн их утгыг олж өгч туслана уу. Мэдээж их сургууль бүр яг нэг л хосод багтана. Бүх замын уртыг тэнцүү $1$ гэж үз.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ ($2 ≤ n ≤ 200 000$, $1 ≤ k ≤ n / 2$) байх буюу Трийлэнд дахь хотуудын тоо ба хос их сургуулиудын тоо. Хотуудыг $1$-c $n$ хүртэл дугаарлагдсан гэж үз.

Хоёр дахь мөрөнд $2k$ ялгаатай бүхэл тоонууд $u_{1}, u_{2}, ..., u_{2k}$ ($1 ≤ u_{i} ≤ n$) байх буюу их сургуулиуд байрласан хотуудын дугаар байна.

Дараагийн $n - 1$ мөрөнд замуудын тайлбар байна. Мөр бүрт хос бүхэл тоо $x_{j}$ ба $y_{j}$ ($1 ≤ x_{j}, y_{j} ≤ n$) байх ба $j$-р зам нь $x_{j}$ ба $y_{j}$ хотуудыг холбож буйг илэрхийлнэ. Бүх зам хос чиглэлтэй. Та зөвхөн эдгээр замуудыг ашиглан дурын хотоос өөр дурын хотруу очиж болно.

Гаралт

Их сургуулиудыг $k$ хос болгон хуваасан хуваалтын нийт зайн боломжит хамгийн их нийлбэрийг хэвлэ.

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

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

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

Тэмдэглэл

Доорх зурагт эхний жишээний хувьд хосуудад хуваах боломжит нэг хуваалтыг харуулсан байна. Хэрвээ та $1$ болон $6$ (улаанаар тэмдэглэсэн) мөн $2$ болон $5$ (хөхөөр тэмдэглэсэн) их сургуулиудыг хооронд нь каблиар холбовол нийт урт нь энэ жишээний хувьд хамгийн их буюу $6$ байна.

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