D. Шинэ жил ба Сантагийн агуулах

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

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

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

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

"Мод" улсын шинэ жил удахгүй болох гэж байна. Нэрнээс нь харахад энэ улс нь $n-1$ ширхэг замаар холбогдсон $n$ хотуудтай ба аль ч хоёр ялгаатай хотын хооронд тэдгээрийг холбосон нэг зам үргэлж байдаг. Хотууд нь $1$-ээс $n$ хүртэлх бүхэл тоонуудаар дугаарлагдсан ба харин замууд нь $1$-ээс $n-1$ хүртэлх бүхэл тоонуудаар дугаарлагдсан. $u$ ба $v$ хотуудын хоорондох маршрут дээрх замын уртыг $d(u, v)$ гэж тодорхойлъё.

"Мод" улсын хүмүүс жил бүр яг нэг зам засварладаг. Үүний үр дүнд нэг замын урт багасдаг. $i$-р жил $r_{i}$-р замын урт нь өмнөх жилийнхээс богиносож $w_{i}$ урттай болсон гэдэг нь мэдэгдэж байгаа.

Яг одоо $1$-р жил буюу $1$ он байгаа гэж үзнэ.

Гурван Санта "Мод" улсын бүх хүүхдэд жил бүр бэлэг өгөхөөр төлөвлөж байна. Үүний тулд тэд зарим нэг бэлтгэл хийх хэрэгтэй, тиймээс тэд $c_{1}$, $c_{2}$, $c_{3}$ гэсэн ялгаатай гурван хот сонгоод, хот бүрд нэг агуулах хийхээр болжээ. $k$-р ($1 ≤ k ≤ 3$) Санта $c_{k}$ хотын агуулахыг хариуцаж авна.

Эдгээрийг барихад $d(c_{1}, c_{2}) + d(c_{2}, c_{3}) + d(c_{3}, c_{1})$ доллар хэрэгтэй. Сантанууд хамгийн бага зардлыг тооцоолох завгүй байгаа тул $1$-ээс $n$ хүртэлх ялгаатай тоонуудын бүх $c_{1}, c_{2}, c_{3}$ гурвалын хувьд дундаж зардлыг тооцоондоо оруулахаар шийжээ. Сантанууд тооцоондоо оруулах зардлын утгыг мэдэхийг хүсч байлаа.

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

Оролт

Эхний мөр нь "Мод" улсын хотуудын тоо болох $n$ ($3 ≤ n ≤ 10^{5}$) бүхэл тоог агуулна.

Дараагийн $n-1$ мөрүүд нь замуудын тодорхойлолтыг агуулна. $i$-р мөрөнд ($1 ≤ i ≤ n - 1$) зайгаар тусгаарлагдсан $a_{i}$, $b_{i}$, $l_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$; $a_{i} ≠ b_{i}$; $1 ≤ l_{i} ≤ 10^{3}$) гурван бүхэл тоо байна. Энэ нь $a_{i}$, $b_{i}$ хотуудыг $i$-р замаар холбосон ба $i$-р зам нь $l_{i}$ урттай гэсэн утгатай.

Дараагийн мөрөнд урт нь өөрчлөгдсөн замын тоо болох $q$ ($1 ≤ q ≤ 10^{5}$) бүхэл тоо байна.

Дараагийн $q$ мөрүүд нь уртын өөрчлөлтийн тодорхойлолтыг агуулна. $j$-р ($1 ≤ j ≤ q$) мөр нь зайгаар тусгаарлагдсан $r_{j}$, $w_{j}$ ($1 ≤ r_{j} ≤ n - 1$; $1 ≤ w_{j} ≤ 10^{3}$) хоёр бүхэл тоог агуулна. Энэ нь $j$-р засвараар $r_{j}$-р замын уртыг $w_{j}$ болгосон гэсэн утгатай. $w_{j}$ нь $r_{j}$-р замын одоогийн уртаас заавал бага байна. Мөн нэг замыг хэд хэдэн удаа засварлаж болно.

Гаралт

$q$ тоонууд хэвлэнэ. Өөрчлөлт бүрийн хувьд "Мод" улсын сүлжээг бий болгоход шаардагдах хүлээгдэж буй зардлыг агуулсан мөр хэвлэнэ. Абсолют буюу харьцангуй алдаа нь $10^{-6}$-ээс хэтрэхгүй бол хариуг зөв гэж үзнэ.

Орчуулсан: Даариймаа

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

Оролт
3
2 3 5
1 3 3
5
1 4
2 2
1 2
2 1
1 1
Гаралт
14.0000000000
12.0000000000
8.0000000000
6.0000000000
4.0000000000
Оролт
6
1 5 3
5 3 2
6 1 7
1 4 4
5 2 3
5
1 2
2 1
3 5
4 1
5 2
Гаралт
19.6000000000
18.6000000000
16.6000000000
13.6000000000
12.6000000000

Тэмдэглэл

Нэгдүгээр жишээг авч үзье. $6$ ширхэг гурвал байна: $(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)$.

$n = 3$ учир бүх гурвалын хувьд сүлжээг бий болгоход хэрэгтэй зардал нь үргэлж $d(1, 2) + d(2, 3) + d(3, 1)$ байна. Тиймээс хүлээгдэж буй зардал $d(1, 2) + d(2, 3) + d(3, 1)$-тай тэнцүү.

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