I can solve this problem in O(N * Log(N)^2). We have to use heavy-light decomposition + persistent segment trees. For each chain of decomposition we have to build segment trees t[i] where t[i] is a tree for first i vertices of chain from top to bottom. At first step we can transform all numbers into numbers from 1 to n. Then build a "start" tree a[i] = 0, for i 1..n . To add a vertice with number X to a tree we just increase value at X. i.e. a[X]++; To answer a query for two vertices X and Y we have to find their LCA Z. Then find about O(log(N)) trees on the way from Z to X and from Z to Y. It is easy to find k-th element of a tree merged from these ones.

I think u can solve it in O(n*log^3(n)). Use binary search with heavy light. Save all numbers in sorted order for each stage in segment tree. It is quite easy to write. But i dont know will it be good for TL.

I found someone's solutions which gets accepted. But I didn't understand the code. Here is link.