Largest palindrome in tree
সময় লিমিট: 3.0 s
মেমরি লিমিট: 512.0 MB
Description
Wasim loves Tree. Fortunately, His friend Roy somehow know it. Roy preapred a problem for him. The problem is very simple,
You are given a tree with \(N\) node and a string \(S\) consisting only lowercase characters (az) of length \(N\) where \(i\)th character represents the character written on \(i\)th node of the tree. Root of the tree is 1 and you need to find out the length of the largest palindromic path from the root. There are also Q query. In each query you have to update \(X\)th node with chararcter \(C\).
Find out the longest palindromic path from the root after perfoming each query.
Palindrome is a word or a phrase that is the same whether you read it backwards or forwards.
Some example of palindrome: a, aa, aba, cbbc, ddddd, edcde etc.
Input
First line takes an integer \(N\) : number of nodes in tree and the length of the string \(S\)
second line takes a string \(S\)
next \(N1\) line takes two integers \(u,v\) : means \(u\)th node has an edge with \(v\)th node
Then take an integer \(Q\) : number of queries
Next \(Q\) line takes an integer \(X\) and a character \(C\)
\(1 <= N <= 1000\)
\(1 <= Q <= 10^5\)
\(1 <= X <= N\)
C consists only lowercase letters.
Output
After perfoming a query print the length of the largest palindromic path from root for all Q queries.
Sample
Input  Output 



intial string S ="ababa";
After first query, S = "abcba", we need to update 3rd node with character c.
all possible path from root 1,
a. string "a", it's a palindrome and length 1.
1 > 2.
a > b. string "ab", it's not a palindrome.
1 > 2 > 3.
a > b > c. string "abc", it's not a palindrome.
1 > 4.
a > b. string "ab", it's not a palindrome.
1 > 5.
a > a. string "aa", it's a palindrome and length 2.
so maximum palindromic path length is 2.
Information
 ID
 1045
 Difficulty
 9
 Category
 (None)
 Tags
 (None)
 # Submissions
 12
 Accepted
 3
 Accepted Ratio
 25%
 Uploaded By
Related
In following contests: