In the question it is no where mentioned that the tree is binary. When I was going through solutions, I find accepted solutions that solved considering the tree to be binary.
Input given in these links is acceptable according to problem statement.
2 Likes
What was the original solution to the problem?Was it heavy light decomposition?
Yes, agreed, Test data was weak 
During the contest, we thought that problem is well known so this might be reason of this many submissions.
I know about segment tree
How did you used segment tree on a tree.How did you convert it to a form of array.
Can you please elaborate your solution.Thanx in advance 
@ayushmnnit16 what i did is firstly i made a dfs traversal of the tree
and assign to each node of the tree the start and the end time of its visit and taking another array to make the inverse of it to get the index of the node in O(1) after making the ordering in tree we can easily make a segment tree query and updates on it in O(log n)
U can have a look at my solution for the clarity :
http://www.codechef.com/viewsolution/4936692
You are still going with same test data or re-evaluating the question with formatted ones?
1 Like