D. Кая ба цасан ширхэг

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

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

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

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

Тольны хэлтэрхийд нүдээ цохьсоныхоо дараа Кая сарнай цэцгийн гоо үзэсгэлэнг сонирхохоо больсон. Одоо тэр харин цасан ширхэг харах дуртай болсон.

Эрт урьд нэгэн цагт тэр $n$ зангилаанаас бүрдэх мод (холбогдсон чиглэлтэй граф) хэлбэртэй маш том цасан ширхэг олсон. Модны үндэс нь $1$ дугаартай. Каяд уг модны бүтэц их сонирхолтой санагдаж байсан.

Зарим нэг судалгаа хийсний дараа Кая сонирхож буй $q$ асуулга бэлдсэн. $i$-р асуулга нь $v_{i}$ оройн дэд модны төвийг олох асуулга байна. Таны зорилго бол бүх асуулгад хариулах юм.

Оройн дэд мод нь уг орой болон уг оройн бүх хүүхэд (шууд болон шууд бус холбогдсон) оройнуудаас бүрдэх модны хэсгийг хэлнэ. Өөрөөр хэлбэл $v$ оройн дэд мод нь үндэс оройноос $u$ орой хүрэх замд $v$ орой оршин байх $u$ оройнуудаас бүрдэнэ.

Модны (эсвэл дэд модны) төв нь нэг орой байх ба хэрвээ бид уг оройг арилгавал холбогдсон хэсгийн хамгийн их хэмжээ нь модны (эсвэл дэд модны) анхны хэмжээнээс ядаж хоёр дахин бага хэмжээтэй байна.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $q$ ($2 ≤ n ≤ 300 000$, $1 ≤ q ≤ 300 000$) байх ба харгалзан анхны модны хэмжээ ба асуулгуудын тоо байна.

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

Дараагийн $q$ мөр бүрт нэг бүхэл тоон утга $v_{i}$ ($1 ≤ v_{i} ≤ n$) байх ба энэ нь бидний төвийг нь олохыг хүсч байгаа дэд модыг тодорхойлох оройн дугаар юм.

Гаралт

Асуулга бүрийн хувьд харгалзах дэд модны төвийн дугаарыг хэвлэ. Хэрвээ хэд хэдэн тохиромжтой орой байвал алийг нь ч хэвлэж болно. Ямар ч дэд мод ядаж нэг төвтэй байна.

Орчуулсан: Г.Мэндбаяр

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

Оролт
7 4
1 1 3 3 5 3
1
2
3
5
Гаралт
3
2
3
6

Тэмдэглэл

Эхний асуулга анхны модны төвийг асуусан ба энэ нь $3$ дугаартай орой юм. Хэрвээ бид $3$ оройг устгавал мод дөрвөн хэсэгт хуваагдах ба $1$ хэмжээтэй хоёр мод болон $2$ хэмжээтэй хоёр мод үүснэ.

Хоёр дахь оройн дэд мод нь зөвхөн уг оройгоос бүрдэх ба хариулт $2$ байна.

$3$ дугаартай орой нь өөрийн дэд модныхоо төв болно.

$5$ дугаартай оройн дэд модны төвүүд нь $5$ болон $6$ дугаартай оройнууд ба эдгээр хариултууд хоёулаа зөвд тооцогдоно.

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