D. Мод ба хүсэлтүүд

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

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

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

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

Танд $n$ оройтой өлгөгдсөн мод өгөгджээ. Модны бүх орой ямар нэг өнгөтэй. Модны оройнууд $1$-с $n$ хүртэл дугаарлагдсан гэнэ. Ингээд $v$ оройн өнгийг $c_v$ гэж тэмдэглэе. Модыг $1$-р оройгоос өлгөсөн.

Энэ бодлого дээр та $m$ хүсэлтэнд хариулах ёстой. Бүх хүсэлт $v_j$, $k_j$ гэх $2$ тоогоор тодорхойлогдох бөгөөд $v_j$ оройн дэд модонд ядаж $k_j$ удаа агуулагдсан хэдэн ялгаатай өнгө байгааг тоолох юм.

Та өлгөгдсөн модны тодорхойлолтыг линкнээс уншиж болно: http://en.wikipedia.org/wiki/Tree_(graph_theory)

Оролт

Оролтын эхний мөрөнд $n$, $m$ ($2 ≤ n ≤ 10^5$; $1 ≤ m ≤ 10^5$) тоо байрлана. Дараагийн мөрөнд $c_1, c_2, ... , c_n$ ($1 ≤ c_i ≤ 10^5$) дараалал өгөгдөнө. Дараагийн $n-1$ мөрт модны холбоосыг илэрхийлэх хос тоонууд байна. $i$-р мөр холбогдсон 2 оройг илэрхийлэх $a_i$, $b_i$ ($1 ≤ a_i, b_i ≤ n$; $a_i ≠ b_i$) тоог агуулна.

Дараагийн $m$ мөрөнд хүсэлтүүд байна. $j$-р мөрөнд $v_j$, $k_j$ ($1 ≤ v_j ≤ n$; $1 ≤ k_j ≤ 10^5$) өгөгдөнө.

Гаралт

Нийт $m$ хүсэлтүүдийн хариуг өгөгдсөн дарааллаар хэвлэнэ.

Орчуулсан: zoloogg

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

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

Тэмдэглэл

Lorem ipsum dolor sit amet, consectetur magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.

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