E. ЭЛСА

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

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

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

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

Танд $n$ орой бүхий үндэстэй мод байв. Модны оройнуудыг $1$-ээс $n$ хүртэлх бүхэл тоонуудаар дугаарлая. Модны үндэс нь $1$ дугаартай орой байх юм.

$v$ орой бүр нь (модны үндэснээс бусад) шууд холбогдох эх орой $p_{v}$-тэй байна. Мөн $v$ орой бүр нь өөрийн бүхэл тоон утга $s_{v}$-тай байна.

Таны даалгавар бол дараах асуултуудыг гүйцэтгэх:

  • $P$ $v$ $u$ ($u ≠ v$). Хэрэв $u$ нь $v$-ын дэд мод дээр байхгүй бол та $p_{v} = u$ болгох юм. Бусад тохиолдолд $p_{u} = v$ болгоно. Уг асуултын дараа граф нь $n$ оройгоос тогтох мод хэвээр байхыг анхаарна уу.
  • $V$ $v$ $t$. $s_{v} = t$ болгоно.

Таны дараах даалгаврыг биелүүлнэ. Эдгээр асуултуудыг гүйцэтгэхээс өмнө болон асуулт болгоны дараа та ижил магадлалаар сонгогдсон $i$ болон $j$ оройнуудын хамгийн бага ерөнхий эх орой дээр бичигдэх хүлээгдэж буй утгыг (ө.х E(x)) тооцоолох юм. $i$ болон $j$ оройнуудын хамгийн бага ерөнхий эх орой гэдэг нь модны үндэснээс $i$ орой хүртэлх зам болон $j$ хүртэлх замууд дээр 2-уулан дээр нь орших хамгийн нам оройг хэлнэ. $i$ and $j$ оройнууд нь ижил байж болохыг анхаарна уу (энэ тохиолдолд тэдгээрийн хамгийн бага ерөнхий эх орой нь тэд өөрсдөө байх юм).

Оролт

Эхний мөрөнд модны оройнуудын тоо болох бүхэл тоо $n$ ($2 ≤ n ≤ 5*10^{4}$) өгөгдөнө.

2-дахь мөрөнд модны ирмэгүүдийг илэрхийлэх $n - 1$ ширхэг бүхэл тоо $p_{2}, p_{3}, ..., p_{n}$ ($1 ≤ p_{i} ≤ n$) өгөгдөнө. Мөн эдгээр тоонууд нь мод үүсгэнэ.

3-дахь мөрөнд модны орой болгон дээр бичигдсэн утгууд болох $n$ ширхэг бүхэл тоо $s_{1}, s_{2}, ... s_{n}$ ($0 ≤ s_{i} ≤ 10^{6}$) өгөгдөнө.

Дараагийн мөрөнд асуултуудын тоо болох бүхэл тоо $q$ ($1 ≤ q ≤ 5*10^{4}$) өгөгдөнө. Дараагийн $q$ мөрийн мөр болгонд бодлогын өгүүлбэрт өгөгдсөн хэлбэртэй асуултууд өгөгдөнө. Асуултуудын аргументууд болох $u$ болон $v$ нь $1$ болон $n$-ын хооронд байна. $V$ төрлийн асуултуудын $t$ аргумент нь $0 ≤ t ≤ 10^{6}$ хязгаартай байна.

Гаралт

Харгалзах хүлээгдэж буй утгуудыг илэрхийлэх $q + 1$ тоо хэвлэнэ. Таны хариулт нь хэрэв абсолют болон харьцангуй алдаа нь $10^{ - 9}$-өөс хэтрэхгүй бол зөвөөр тооцогдоно.

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

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

Оролт
5
1 2 2 1
1 2 3 4 5
5
P 3 4
P 4 5
V 2 3
P 5 2
P 1 4
Гаралт
1.640000000
1.800000000
2.280000000
2.320000000
2.800000000
1.840000000

Тэмдэглэл

$P$ $v$ $u$ асуултын хувьд хэрэв $u$ нь $v$-ын дэд мод дээр байвал та $p_{u} = v$ болгох ёстойг анхаарна уу. Ийм байх тохиолдол нь бодлогын жишээний сүүлийн асуулт дээр гарч ирнэ.

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