Hello!

I am solving a problem where a rooted tree with N vertices is given, each vertex has a value V <= 10^9, and i have to answer M queries. Each of the queries has the format (V,K), and i have to answer which is the K-th smallest value in the subtree rooted in vertex V. The limits for N,M are 10^5.

My current approach solves almost every instance of the problem (O(N log N) average) but fails when the tree degenerates to a linked list (O(N^2 log N) worst case). I store every query so i can answer all them after i run my algorithm. I process the tree from the leaves up to the root using topological sort, and when i am processing some vertex, i merge the leaves' subtrees values using heapsort (found it to be faster than mergesort, but still slow if the tree is a linked list), and answer every query related to this vertex. After every vertex has been processed, i iterate over the answer array and print the results.

Can anyone help me with a better approach, or point some property that can help my solution so it doesn't get TLE verdict?

Thanks in advance.

EDIT : problem solved, used the idea given by ffao.

Original statement : https://www.urionlinejudge.com.br/judge/en/problems/view/1695

My code : http://pastebin.com/ncWeC102