Prerequisite : Tree, Depth First Search, Math, 2d – array, String Algorithm , Constructive Algorithm.
Problem statement summary : You are given a tree with N node and a string S consisting only lowercase characters (a-z) 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.
Solution :
1st Observation : You can see N = 1000 only and there are exactly N paths from root 1.
If N = 4 that means exactly 4 paths from root node 1.
First we need to store all possible path from node 1.
2nd Observation :
Once we store all possible path then we check how many character match each path. Let’s see an example:
Some possible path from root 1,
i. 1 -> 2
a a
ii. 1 -> 2 -> 3
a a b
iii. 1 -> 2 -> 3-> 4
a a b a

path from 1 to 2 , matching character 2 and node 1 is depend on 2 and node 2 is depend on 1.(think palindrome). Check colorings same color depend on each other.
Path from 1 to 3, matching character 1 and node 1 is depend on node 3 and node 3 is depend on node 1, node 2 is depend on node 2. (think palindrome).
If we calculate this way,
Path i, matching = 2 and path length =2
Path ii, matching =1 and path length =3
Path iii, matching = 2 and path length = 4,
Note that if the matching is equal to path length then we can call it path is a palindromic path.
If we need to update node 3 with character a,
Some possible path from root 1,
i. 1 -> 2
a a
ii. 1 -> 2 -> 3
a a a
iii. 1 -> 2 -> 3-> 4
a a a a
then we should update each path by,

• path i does not have node 3, we can skip and matching =2 and length of the path =2, if(matching ==length of the path), it is a palindromic path.
• path ii exist node 3, previous matching =1 and current matching = 3, because (node 1 and node 3 same character), we should need to increase by 2. Length of the path is 3 and matching = 3 , so it’s a palindromic path.
• path iii exist node 3, previous matching =2 and current matching = 4, because (node 2 and node 3 has same character), we should need to increase by 2. Length of the path is 4 and current matching = 4, so it’s a palindromic path.
  You can use 2d array for storing every path, each node dependable position so that when we need to update we only update this position not fully each path.
  Time complexity : O ( Q * N).