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 N1 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 /sample output for details.
Sample Input
Sample Output
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
NO
YES
YES
YES
NO
In the 2^{nd} query, the formed palindrome can be “badab” or “abdba”
In the 3^{rd} query, there is only 1 character “d”, which is palindrome.
hide comments
k_best02:
20171017 10:59:57
26 fenwick tree :) 

hodobox:
20170804 19:49:23
HLD is not needed to solve in MlogN :) Last edit: 20170804 19:49:43 

lu:
20170513 16:55:15
It is easy to solve it with LCT 

Acc:
20160824 19:08:24
got "WA" instead of "SIGSEGV" by declare lack of space in array. Hope it help.

Added by:  Md. Najim Ahmed 
Date:  20151210 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 