Мод Дээрх Зоос Цуглуулалт II

2s

512MB

2167

0%

Advanced Graph Problems

$n$ орой бүхий мод өгөгдсөн. Зарим орой зоостой.

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

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

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

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

Хоёр дахь мөрөнд $n$ бүхэл тоо $c_1, c_2,\dots, c_n$ . $c_i = 1$ бол $i$ орой зоостой. $c_i = 0$ бол $i$ орой зоосгүй. Хамгийн багадаа нэг орой зоостой гэж үзэж болно.

Дараагийн $n-1$ мөрөнд ирмэгүүд. Мөр бүр $a$ ба $b$ бүхэл тоонуудыг агуулна: $a$ болон $b$ оройнуудын хооронд ирмэг бий.

Эцэст нь $q$ мөрөнд хүсэлтүүд. Мөр бүр $a$ ба $b$ бүхэл тоонуудыг агуулна: эхлэх болон төгсгөх орой.

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

$q$ бүхэл тоо хэвлэ: хүсэлтүүдийн хариултууд.

Хязгаарлалт

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

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

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