Given a rooted tree having N nodes. Root node is node 1. Each ith node has some value , val[i] associated with it.

For each node i (1<=i<=N) we want to know MEX of the path values from root node to node i.

MEX of an array is smallest positive integer not present in the array, for instance MEX of {1,2,4} is 3

Example : Say we are given tree with 4 nodes. Value of nodes are [1,3,2,8] and we also have parent of each node i (other than node 1 as it is the root node). Parent array is defined as [1,2,2] for this example. It means parent of node 2 is node 1, parent of node 3 is node 2 and parent of node 4 is also node 2.

Node 1 : MEX(1) = 2 Node 2 : MEX(1,3) = 2 Node 3 : MEX(1,3,2) = 4 Node 4 : MEX(1,3,8) = 2 Hence answer is [2,2,4,2]

In worst case total number of Nodes can be upto 10^6 and value of each node can go upto 10^9.

Can anyone tell the optimal way to solve this problem?