Question C

question_c.txt

Deskripsi
Diberikan sebuah rooted tree yang terdiri dari N node dengan node 1 sebagai root dari tree tersebut. Di setiap node terdapat salah satu karakter dari ‘a’ sampai ‘z’.

Diberikan Q buah query yang terdiri dari 2 tipe :

Tipe pertama meng-update karakter-karakter yang berada pada subtree u menjadi 1 karakter setelahnya. Asumsikan karakter-karakter tersebut bersifat sirkular yang artinya setelah diupdate karakter ‘z’ akan menjadi karakter ‘a’
Tipe kedua,diberikan sebuah string,tentukan apakah kita dapat membentuk string tersebut menggunakan karakter-karakter yang berada pada subtree node u.
Format Masukan
Baris pertama berisi 2 buah bilangan N dan Q. Banyaknya node dan banyaknya query

Baris berikutnya berisi N - 1 bilangan Ai dimana Ai berarti parent dari node i - 1 pada tree.

Baris berikutnya berisi N buah karakter Bi dimana Bi merupakan karakter yang ada pada node i

Q baris berikutnya berisi query-query dengan format:

“1 u” untuk query tipe pertama. Dengan u merupakan root dari subtree yang akan diupdate
“2 u s” untuk query tipe kedua. Dengan u merupakan root dari subtree serta s adalah string yang akan dibentuk
Format Keluaran
Untuk setiap query tipe 2,keluarkan “YA” jika bisa membentuk string yang diberikan dan “TIDAK” jika tidak.

Contoh Masukan
12 5
1 1 1 2 2 2 3 8 8 6 6
a a k b c i c m a u n t
2 1 aku
2 2 cinta
2 1 kamu
1 1
2 1 kamu
Contoh Keluaran
YA
YA
YA
TIDAK
Batasan
Untuk semua subsoal berlaku
1 ≤ N,Q ≤ 105
1 ≤ Ai ≤ N
Bi hanya terdiri dari karakter ‘a’ – ‘z’
|s| ≤ N
1 ≤ u ≤ N
Total |s| tidak lebih dari 5*105
Subsoal
Subsoal 1 (10 Poin)
1 ≤ N,Q ≤ 103
A_i = i untuk 1 ≤ i ≤ N
Subsoal 2 (13 Poin)
A_i = i untuk 1 ≤ i ≤ N
Tidak ada query tipe 1
Subsoal 3 (32 Poin)
A_i = i untuk 1 ≤ i ≤ N
Subsoal 4 (12 Poin)
1 ≤ N,Q ≤ 103
Subsoal 5 (15 Poin)
Tidak ada query tipe 1
Subsoal 6 (18 Poin)
Tidak ada batasan tambahan.