B. Тэг мод

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

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

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

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

Мод бол $n$ оройтой, яг $n-1$ ирмэгээр холбогдсон, дурын 2 оройн хооронд хамгийн богино зам цор ганц байдаг граф юм.

$T$ модны дэд мод гэдэг нь $T$ модны орой болон ирмэгийн дэд олонлогоос тогтсон мод байна.

Танд $n$ оройтой мод өгөгдсөн. Оройнууд нь $1$-ээс $n$ хүртэл дугаардагдсан. Мөн орой бүр дээр нэг нэг тоо бичигдсэн байгаа. Эхэндээ $i$-дэх орой дээр бичигдсэн тоо нь $v_i$ байсан. Нэг ээлжин дээр дараах үйлдлүүдийг хийж чадна.

  1. Өгөгдсөн модноос дээрх тоо нь $1$ байх орой агуулсан дэд мод сонгон авна.
  2. Сонгосон дэд модон агуулагдаж байгаа бүх тоог $1$-ээр ихэсгэнэ нэг бол багасгана.

Өгөгдсөн модны бүх орой дээрх тоог $0$ болгох хамгийн цөөн үйлдлийн тоог ол.

Оролт

Эхний мөрөнд оройн тоо $n(1≤n≤10^5)$. Дараагийн $n-1$ мөрөнд хоорондоо холбогдсон хоёр оройн дугаар $a_i,\ b_i(1≤a_i,b_i≤n;\ a_i≠b_i)$ байрлана. Оролтонд баталгаатай мод өгөгдөнө.

Сүүлйин мөрөнд оройнууд дээр байрлах тоо $v_1,\ v_2,...,\ v_n(|v_i|≤10^9)$ агуулагдана.

Гаралт

Бодлогыг шийдэж болох хамгийн бага үйлдлийн тоог хэвлэнэ.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Говьхүү

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

Оролт
3
1 2
1 3
1 -1 1
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...