D. Машмок ба усны сав

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

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

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

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

Машмок шинэ тоглоом тоглож байна. Тоглоомын эхэнд түүнд $k$ литр ус мөн $p$ зоос байна. Нэмж хэлэхэд түүнд мөн $m$ оройгоос бүрдэх үндэстэй мод (чиглэлгүй холбогдсон циклгүй граф) байна. Модны орой бүр анх хоосон байх усны сав агуулсан байна.

Тоглоом эхлэхэд Машмок усны савнуудаас (үндсээс бусад) хэд хэдийг сонгох ($k$-с их биш) ба сонгосон сав бүртээ яг $1$ литр ус юүлнэ. Ингээд савнууд усгүй болох хүртэл дараах үйл явц явагдана.

  • Үйл явц хэд хэдэн үйлдлээс тогтоно.
  • Үйлдэл бүрийн эхэнд Машмок бүх савны тагийг нээнэ. Тэгээд Машмок уг үйлдлийн туршид зарим савны тагийг хаана (тэр үндэс дээр байгаа савны тагийг хаахгүй). Хаалга нь хаалттай саван дахь усны хэмжээг $w$ гэж тэмдэглэе, Машмок уг үйлдлийн хугацаанд уг савыг тагласныхаа төлөө $w$ зоос төлнө.
  • Модны оройнуудын гүнээр нь эрэмбэлэсэн (өсөхөөр) жагсаалтыг $x_{1}, x_{2}, ..., x_{m}$ гэж тэмдэглэе. Энэ жагсаалтад байгаа оройнуудыг дарааллаар нь нэг нэгээр нь авч үзнэ. Эхлээд $x_{1}$ (өөрийнхөө үндэс) оройг хоослоно. Тэгээд $x_{i}$ $(i > 1)$ орой бүрийг, хэрвээ уг оройд байгаа сав хаалттай бол уг оройг алгасаад бусад бүх $x_{i}$ оройд байгаа савны бүх усыг уг оройн эцэг оройн савруу юүлнэ (эцэг зангилааны сав хаалттай байсан ч).

Мод хоосон болтол $l$ үйлдэл хийгдсэн гэе. $i$-р үйлдлийн дараах үндэс оройн саванд байгаа усны хэмжээг $w_{i}$ гэж тэмдэглэе, тэгээд Машмок $max(w_{1}, w_{2}, ..., w_{l})$ доллар хожно. Машмок дээрх тоглоомийг тоглоод хамгийн ихдээ хэдэн доллар хожиж чадахаа мэдэхийг хүсч байна. Тэр таныг энэ утгыг олж өгөхийг хүсч байна.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан гурван бүхэл тоон утга $m, k, p (2 ≤ m ≤ 10^{5}; 0 ≤ k, p ≤ 10^{9})$ байна.

Дараагийн $m - 1$ мөр бүрт зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ m; a_{i} ≠ b_{i})$ байх буюу модны ирмэгүүд юм.

Модны оройнууд 1-c $m$ хүртэл дугаарлагдсан. Модны үндэс 1 дугаартай.

Гаралт

Гаралтанд Машмокийн таниас асуусан тоог илэрхийлэх нэг бүхэл тоог хэвлэ.

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

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

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

Тэмдэглэл

Эхний жишээний модыг доорх зурагт үзүүлсэн байна. хар, улаан, хөх өнгөнүүд нь 0, 1, 2 литр устай оройнуудад харгалзана.

Хамгийн их хэмжээний мөнгө олж авах нэг арга бол 3 болон 4 дугаартай орой бүрээс нэг литр ус авах юм. Эхлэлийн төлвийг доорх зурагт үзүүлэв.

Тэгээд эхний үйлдэлд Машмок гуравдугаар оройны хаалгыг хаахын тулд 1 зоос төлнө. Эхний үйлдлийн дараах модыг доорх зурагт үзүүлсэн байна.

Хоёр дахь үйлдлийн дараа үндэс оройд доор зурагт үзүүлсэнчлэн 2 литр ус үлдэнэ.

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