C. Петя ба Мод

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

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

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

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

Нэгэн шөнө, хүнд ажлын дараа, Петя хар даржээ. Түүний зүүдэнд хоёртын хайлтын мод байв. Гэхдээ энэ нь түүнийг айлгасан зүйл биш юм. Аймшигтай зүйл нь гэвэл Петя хайхыг хүссэн элементээ хайж чадахгүйд байв. Петя олон удаа түлхүүрүүдийг хайж удаан суусан боловч буруу газарт очсоор байгаад толгой нь гашлав. Яг цөхрөхийн алдад алдаагаа ухаарч : Петягийн хайж байгаа түлхүүр болгон нь модонд байдаггүй бөгөөд хайх явцад яг нэг алдаа гардаг байв. Тэгээд Петя "Энэ асуудал бишээ", "Яагаад хайж байгаад олдсон түлхүүрүүдийн хүсэмжит утгыг тооцоолж болохгүй гэж?" гэж бодоод яг хийх гэж байхад Петя сэрчихэв.

Таньд хоёртын хайлтын мод өгөгдсөн бөгөөд нүднүүдэд тоо хадгалсан байгаа. Энэ тоонуудыг нүднүүдийн түлхүүр гэнэ. Энэ нүдний хүүхдүүдийн тоо $0$ эсвэл $2$ байна. Хэрэв $0$ бол энэ нүдийг навч, $2$ бол энэ нүдийг дотоод нүд гэнэ. Дотоод нүд зүүн болон баруун хүүхэдтэй. Зүүн хүүхдийн түлхүүр энэ нүдний түлхүүрээс эрс бага байх ба баруун хүүхдийн түлхүүр энэ нүдний түлхүүрээс эрс их байна. Бас аль ч нүдний зүүн дэд модны түлхүүрүүд энэ нүдний түлхүүрээс эрс бага байх ба баруун дэд модны түлхүүрүүд энэ нүдний түлхүүрээс эрс их байна.

Мөн хайлтын түлхүүрүүдийг өгсөн ба бүгд ялгаатай ба модны түлхүүрүүдээс өөр байна. Түлхүүр болгоны хувьд модонд хайлт хийнэ. Модноос хайлт хийхэд дараах дарааллаар хайна : анхандаа модны үндэс дээр байгаа, хэрэв тухайн нүдний түлхүүр одоогийн хайж байгаа түлхүүрээс их бол зүүн хүүхэдрүү, үгүй бол баруун хүүхэдрүү шилжинэ. Дээрх үйлдлийг навчин дээр очих хүртэл давтана. Хайж байгаа түлхүүр модонд байхгүй. Энэхүү хайлтын үр дүн нь навчны түлхүүр юм.

Хайлт болгоны явцад яг нэг алддаг ба түүнээс хойш алддаггүй. Хэрэв бүх нүдэндэх алдах боломж тэнцүү магадлалтай бол бүх хайлтын үр дүнгийн хүсэмжит утгыг (дундаж утгыг) олж өгнө үү. Энэ нь хайх явцдаа яг нэг удаа алддаг байхаар бүх хайлтын үр дүнгийн дундаж утгыг тооцоолох юм.

Оролт

Эхний мөрөнд $n$ ($3 ≤ n < 10^{5}$) сондгой тоо, модны нүдний тоо. Дараагийн $n$ мөрөнд нүдний мэдээлэл байна. $(i + 1)$-р мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо, эхний тоо $i$-р нүдний эцэг, хоёрдох тоо нь $i$-р нүдний түлхүүр байна. Дараагийн мөрөнд $k$ ($1 ≤ k ≤ 10^{5}$) бүхэл тоо, хайх түлхүүрүүдийн тоо, дараагийн $k$ мөр болгонд хайх түлхүүрийн тоо өгөгдөнө.

Бүх түлхүүрүүдийн утга $10^{9}$-с хэтрэхгүй. Бүх $n + k$ түлхүүрүүд ялгаатай.

Нүднүүдийг $1$-ээс $n$ хүртэл дугаарласан. Үндэсний эцэг нь "-1" (хашилтгүйгээр) байна. Өгөгдөл хоёртын хайлтын мод байна. Үндэснээс бусад бүх нүдний түлхүүрийг эцгийнх нь түлхүүртэй харьцуулан тухайн нүдний зүүн эсвэл баруун хүүхэд болохыг мэдэж болно.

Гаралт

$k$ мөр тус бүрд хариу болгоныг 9 орны нарийвчлалтай хэвлэ.

Орчуулсан: Б.Алтангэрэл

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

Оролт
7
-1 8
1 4
1 12
2 2
2 6
3 10
3 14
1
1
Гаралт
8.0000000000
Оролт
3
-1 5
1 3
1 7
6
1
2
4
6
8
9
Гаралт
7.0000000000
7.0000000000
7.0000000000
3.0000000000
3.0000000000
3.0000000000

Тэмдэглэл

Эхний жишээнд 1 түлхүүрийг хайлтын явцад яг нэг алдаа гардаг байхаар хайхад дараах боломжит замууд гарч ирнэ : (1, 2, 5) ба (1, 3, 6), хаалтан доторх тоог үндсээс навч хүртэл бичсэн. Навчнуудын түлхүүрүүд харгалзан 6 ба 10-тай тэнцүү, ийм учраас хариу 8 байна.

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