D. Хамилтонианын холбогдож буй мод

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

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

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

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

$n$ хотуудын бүлэг нь замуудын сүлжээгээр холбогджээ. Эдгээр хос хотууд бүрийн хооронд чиглэлгүй зам байх ба нийт зам байв. Ямар ч замыг туулж өнгөрөхөд яг $y$ секунд зарцуулдаг.

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

Анхны замын сүлжээний ямар нэг холбогдож буй мод нь сонгогдсон байв. Уг модны зам бүрийн хувьд уг замыг туулж өнгөрөхөд зарцуулах хугацаа нь $y$-ээс $x$ секунд болж өөрчлөгджээ. $x$ нь $y$-ээс бага байх албагүй болохыг анхаарна уу.

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

Оролт

Эхний мөрөнд 3 бүхэл тоо $n$, $x$ болон $y$ ($2 ≤ n ≤ 200 000, 1 ≤ x, y ≤ 10^{9}$) өгөгдөнө.

Дараагийн $n - 1$ мөрийн мөр болгонд холбогдож буй модны нэг замын тайлбар өгөгдөнө. Эдгээр мөрүүдийн $i$-дахь мөрөнд 2 бүхэл тоо $u_{i}$ болон $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$) өгөгдөх ба эдгээр нь $i$-дахь ирмэгээр холбогдож буй хотуудын дугаарыг илэрхийлнэ. Мөн эдгээр замууд нь холбогдож буй мод үүсгэнэ.

Гаралт

Бүх хотуудаар яг нэг удаа зорчиход шаардагдах секундийн хамгийн бага тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

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

Тэмдэглэл

Эхний жишээнд холбогдож буй модны замыг туулахад $2$ секунд ба бусад замуудыг туулахад $3$ секунд байна. Оновчтой маршрутын нэгэн жишээ нь байна.

2-дахь жишээнд бидэнд өмнөх жишээтэй ижилхэн холбогдож буй мод байгаа боловч холбогдож буй модны замыг туулахад $3$ секунд ба бусад замуудыг туулахад $2$ секунд байна. Оновчтой маршрутын нэгэн жишээ нь байна.

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