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.


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.


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


5 4

1 5

6 3

1 7

5 6

6 2



1 1

1 5

1 3

0 7 a

1 1

0 4 z

1 5








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

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


hide comments
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
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY