PLNDTREE - Palindrome in a Tree


John has got a tree with N vertices. The vertices are numbered from 1 to N. He considers vertex 1 as the root of the tree. Each vertex of the tree contains a character C.

Now John is doing a weird experiment with this tree.

He often changes the character of a node in the tree and then sometimes he randomly selects a node v and tries to form a palindrome with all the characters in the subtree of node v.

But since John is very busy man and has a lot of other important experiments to do he needs your help on this one.

Input

First line of the input contains an integer N (1 <= N <= 100000) denoting the number of vertices.

Next N-1 lines contains two integers A and B (1 <= A, B <= N) which means there is an edge between vertex A and B.

Next line contains a string of length N. The ith character of this string denotes the character in node i.

Then there will be an integer M (1 <= M <= 100000) in a separate line denoting the number of queries. Next M lines will contain a query.

Each query will be in one of the following form:

0 x C: which means the character of node x has been changed to C.

1 x: which means you are asked to answer if a palindrome can be formed with all the characters in the sub tree of node x. There will be at least one query of this type.

Output

For each query of the form “1 x” print “YES” if a palindrome can be formed with all the characters in subtree of node x. Otherwise print “NO” (without the quotes).

All the characters in the input will be small letters of English alphabet, i.e. a, b, c ... x, y, z.

See sample input / output for details.

Sample

Input
7
5 4
1 5
6 3
1 7
5 6
6 2
abdaabc
7
1 1
1 5
1 3
0 7 a
1 1
0 4 z
1 5

output
NO
YES
YES
YES
NO

Explanation

In the 2nd query, the formed palindrome can be “badab” or “abdba”.

In the 3rd query, there is only 1 character “d”, which is a palindrome.


hide comments
abhimanyu_1998: 2019-12-17 14:40:59

didnt pass in CPP14 , AC in CPP , dont know why.

k_best02: 2017-10-17 10:59:57

26 fenwick tree :)

hodobox: 2017-08-04 19:49:23

HLD is not needed to solve in MlogN :)

Last edit: 2017-08-04 19:49:43
lu: 2017-05-13 16:55:15

It is easy to solve it with LCT

Acc: 2016-08-24 19:08:24

got "WA" instead of "SIGSEGV" by declare lack of space in array. Hope it help.
Use heavy light tree to solve it in nlogn.


Added by:Md. Najim Ahmed
Date:2015-12-10
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY