Компанийн Хүсэлт II

2s

512MB

1420

0%

Tree Algorithms

Компанид $n$ ажилтан байх бөгөөд мод хэлбэрийн шатлал үүсгэнэ: ерөнхий захиралаас бусад ажилтан бүр захиралтай.

Дараах хэлбэрийн $q$ хүсэлтийг боловсруул: шатлалд $a$ , $b$ ажилтнуудын хамгийн ойрын захирал хэн бэ?

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n$ , $q$ байна: ажилтан ба хүсэлтийн тоо. Ажилтнууд $1,2,\dots,n$ -ээр дугаарлагдана, $1$ дугаар ажилтан ерөнхий захирал.

Дараагийн мөрөнд $n-1$ бүхэл тоо $e_2,e_3,\dots,e_n$ байна: $2,3,\dots,n$ дугаар ажилтан бүрийн захирал.

Сүүлд нь $q$ мөр нь хүсэлтүүдийг тодорхойлно. Мөр бүрт хоёр бүхэл тоо $a$ , $b$ байна: $a$ , $b$ ажилтнуудын хамгийн ойрын захирал хэн бэ?

Гаралтын формат

Хүсэлт бүрийн хариултыг хэвлэ.

Хязгаарлалт

$1 \le n,q \le 2 \cdot 10^5$
$1 \le e_i \le i-1$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

3
1
1

0.1 / 64 KiB

Редактор уншиж байна...