Codeforces Round #804 (Div. 2)
3 өдрийн дараа |
E. Шинэ жилийн мод
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Шинэ жилийн өдрүүд дууссан ч Рэша шинэ жилийн сүлд модоо буулгахыг хүссэнгүй. Тэр шинэ жилийнхээ модыг дахин чимэглэхээр түүний дотны найзууд болох Керим болон Гюралыг туслуулахаар дуудсан.
Шинэ жилийн мод нь чиглэлгүй $n$ оройтой ба үндэс нь $1$-р орой юм.
Та хоёр төрлийн үйлдлийг гүйцэтгэнэ:
- $v$ оройн дэд модонд байгаа бүх оройг $c$ өнгөтэй болгож соль.
- $v$ оройн дэд модонд байгаа ялгаатай өнгөнүүдийн тоог ол.
Оролт
Эхний мөрөнд хоёр бүхэл тоон утга $n, m$ ($1 ≤ n, m ≤ 4*10^{5}$) -- Модон дахь оройн тоо болон үйлдлүүдийн тоо .
Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утга $c_{i}$ ($1 ≤ c_{i} ≤ 60$) -- $i$ дахь оройн өнгө.
Дараагийн $n - 1$ мөр тус бүрт хоёр бүхэл тоон утга $x_{j}, y_{j}$ ($1 ≤ x_{j}, y_{j} ≤ n$) -- $j$-дэх ирмэгийн оройнууд. Энэ нь танд зөв чиглэлгүй мод өгөгдсөн гэсэн үг.
Сүүлийн $m$ мөр нь үйлдлүүдийн тодорхойлолтыг агуулсан. Тодорхойлолт бүр бүхэл тоон утга $t_{k}$ ($1 ≤ t_{k} ≤ 2$)-р эхлэдэг -- $k$-дэх асуултын төрөл. Эхний төрлийн үйлдлүүд нь дараах хоёр бүхэл тоон утгуудтай $v_{k}, c_{k}$ ($1 ≤ v_{k} ≤ n, 1 ≤ c_{k} ≤ 60$) – дэд мод нь $c_{k}$ өнгөөр будагдах оройн дугаар. Хоёр дахь төрлийн үйлдлүүд нь дараах бүхэл тоон утгатай $v_{k}$ ($1 ≤ v_{k} ≤ n$) – дэд модонд нь хэдэн ялгаатай өнгө орсныг олох оройн дугаар.
Гаралт
Хоёр дахь төрлийн үйлдэл бүрийн хувьд бүхэл тоон утга $a$-г хэвлэ – үйлдэлд өгөгдсөн оройн дэд модон дахь ялгаатай өнгөний тоо
Оролтонд байгаа үйлдлүүдийн дарааллаар тоо бүр тусдаа мөрөнд хэвлэгдсэн байх ёстой.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
7 10 1 1 1 1 1 1 1 1 2 1 3 1 4 3 5 3 6 3 7 1 3 2 2 1 1 4 3 2 1 1 2 5 2 1 1 6 4 2 1 2 2 2 3
Гаралт
2 3 4 5 1 2
Оролт
23 30 1 2 2 6 5 3 2 1 1 1 2 4 5 3 4 4 3 3 3 3 3 4 6 1 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 4 11 6 12 6 13 7 14 7 15 7 16 8 17 8 18 10 19 10 20 10 21 11 22 11 23 2 1 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 4 1 12 1 1 13 1 1 14 1 1 15 1 1 16 1 1 17 1 1 18 1 1 19 1 1 20 1 1 21 1 1 22 1 1 23 1 2 1 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 4
Гаралт
6 1 3 3 2 1 2 3 5 5 1 2 2 1 1 1 2 3