E. Тараагч мод

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

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

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

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

Иахуб моднуудад маш их дуртай. Саяхан тэр тараагч мод хэмээх нэгэн сонирхолтой модыг олж мэдсэн юм. Энэ мод нь $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг оройноос бүрдэх бөгөөд $i$ орой бүрийн анхны утга нь $a_{i}$ байна. $1$-р орой бол модны үндэс юм.

Энэ мод нэг онцгой чанартай: $i$ оройн утгыг $val$ утгаар нэмэх үед, тухайн $i$ оройн бүх хүүхэд оройнуудын утга $-val$ утгаар нэмэгдэнэ. $i$ оройн хүүхэд оройн утга $-val$-р нэмэгдэх үед, $i$ оройн хүүхэд оройн бүх хүүхэд оройн утга $-(-val$) утгаар гэх мэтчилэн нэмэгдэнэ гэдгийг анхаараарай. Энэ мод хэрхэн ажилладаг талаар илүү сайн ойлгохыг хүсвэл жишээний тайлбарыг харна уу.

Энэ модны хувьд хоёр төрлийн хүсэлт боловсруулж болно:

  • "1 x val" - $x$ оройн утга $val$-аар нэмэгдэнэ
  • "2 x" - $x$ оройн одоогийн утгыг хэвлэнэ.

Иахубд модыг илүү сайн ойлгоход нь туслахын тулд та дээрх төрлийн $m$ ширхэг хүсэлтэд хариулах ёстой.

Оролт

Эхний мөр нь $n$, $m$ $(1 ≤ n, m ≤ 200000)$ хоёр бүхэл тоог агуулна. Хоёр дахь мөр нь $n$ ширхэг $a_{1}$, $a_{2}$, ..., $a_{n}$ $(1 ≤ a_{i} ≤ 1000)$ бүхэл тоонуудыг агуулна. Дараагийн $n-1$ мөр бүр нь $v_{i}$ ба $u_{i}$ $(1 ≤ v_{i}, u_{i} ≤ n)$ бүхэл тоонуудыг агуулна. Энэ нь $v_{i}$ ба $u_{i}$ оройнуудын хооронд ирмэг байгааг илэрхийлнэ.

Дараагийн $m$ мөрүүд нь дээр тодорхойлсон төрлийн хүсэлтүүдийг агуулна. Бүх хүсэлт дараах хязгаарлалтуудыг хангасан байх ёстой: $1 ≤ x ≤ n, 1 ≤ val ≤ 1000$.

Гаралт

Хоёрдугаар төрлийн хүсэлт бүрийн хариуг ($x$ оройн утгыг хэвлэнэ) тусдаа мөрүүдэд хэвлэнэ. Хүсэлтүүдийн хариуг хэвлэхдээ оролтод өгөгдсөн дарааллаар хэвлэнэ.

Орчуулсан: Даариймаа

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

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

Тэмдэглэл

Эхлээд оройнуудын утга $[1, 2, 1, 1, 2]$ байна.

$2$-р оройн утга дээр $3$-ыг нэмнэ. Ингээд $2$-р оройн хүүхэд оройнууд болох $4$-р ба $5$-р оройнуудын утга дээр $-3$-ыг нэмнэ. Өөр хүүхэд орой байхгүй учраас оройнуудын утга $[1, 5, 1, -2, -1]$ болсон байна.

Дараа нь $1$-р оройн утга дээр $2$-ыг нэмнэ. $1$ оройн хүүхэд оройнууд болох $2$-р ба $3$-р оройнуудын утга дээр $-2$-ыг нэмнэ. $2$-р орой цааш тарж $2$-р оройн хүүхэд оройнууд болох $4$-р ба $5$-р оройнуудын утга дээр $2$-ыг нэмнэ. $3$-р орой хүүхэдгүй учраас цааш тарахгүй. Ингээд оройнуудын утга $[3, 3, -1, 0, 1]$ болно.

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

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