C. Өөрчлөгдөж буй мод

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

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

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

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

Танд $1$-ээс $n$ хүртэл дугаарлагдсан $n$ оройгоос тогтох үндэстэй мод өгөгдөв. Модны үндэс нь $1$ дугаартай орой байна.

Анхандаа бүх оройнууд нь $0$ гэсэн тоог агуулна. Дараа нь $q$ ширхэг асуултууд өгөгдөх ба асуулт нь болгон нь дараах 2 төрлийн нэг нь байх юм:

  • Асуултын хэлбэр: $1$ $v$ $x$ $k$. Уг асуултад хариулахдаа та $v$ дугаартай орой дээрх тоон дээр $x$ тоог нэмнэ; $v$ дугаартай оройноос $1$ зайтай байх үрийн оройнууд дээрх тоонууд дээр $x - k$-г нэмнэ гэх мэтчилэн $v$ дугаартай оройноос $i$ зайтай байх үрийн оройнууд дээрх тоонууд дээр $x - (i*k)$-г нэмэх юм. 2 оройны хоорондох зай гэдэг нь уг оройнуудын хоорондох хамгийн богино зам дээрх ирмэгүүдийн тоог хэлнэ.
  • Асуултын хэлбэр: $2$ $v$. Уг асуултад хариулахдаа та $v$ дугаартай орой дээр бичигдсэн тоог $1000000007$ $(10^{9} + 7)$ модулаар бодон хэвлэх юм.

Оролтод өгөгдсөн асуултуудыг гүйцэтгэнэ үү.

Оролт

Эхний мөрөнд модны оройнуудын тоог илэрхийлэх бүхэл тоо $n$ ($1 ≤ n ≤ 3*10^{5}$) өгөгдөнө. 2-дахь мөрөнд $n - 1$ ширхэг бүхэл тоо $p_{2}, p_{3}, ... p_{n}$ ($1 ≤ p_{i} < i$)-ууд өгөгдөх ба энд $p_{i}$-аар модны $i$ дугаартай оройны эх оройн дугаарыг тэмдэглэв.

3-дахь мөрөнд асуултуудын тоог илэрхийлэх бүхэл тоо $q$ ($1 ≤ q ≤ 3*10^{5}$) өгөгдөнө. Дараагийн $q$ мөрөнд асуултууд өгөгдөх ба мөр болгонд нэг асуулт өгөгдөнө. Мөрөнд өгөгдөх эхний тоо нь асуултын төрлийг илэрхийлэх $type$ тоо өгөгдөнө. Хэрэв $type = 1$ бол араас нь зайгаар тусгаарлагдсан бүхэл тоонууд $v, x, k$ ($1 ≤ v ≤ n$; $0 ≤ x < 10^{9} + 7$; $0 ≤ k < 10^{9} + 7$) өгөгдөнө. Хэрэв $type = 2$ бол араас нь дээр нь бичигдсэн тооны утгыг олох ёстой оройг илэрхийлэх бүхэл тоо $v$ ($1 ≤ v ≤ n$) өгөгдөнө.

Гаралт

2-р төрлийн асуулт бүрийн хувьд дан мөрөнд тухайн орой дээрх тоог хэвлэнэ. Уг тоог $1000000007$ $(10^{9} + 7)$ модулаар бодон хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
3
1 1
3
1 1 2 1
2 1
2 2
Гаралт
2
1

Тэмдэглэл

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

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