This problem can be solved without the constraints \(k\leq 10\). We will briefly introduce the approaches.

\(O(N\log^2 N+Q\log N)\) solution

The approach is the same as the original editorial. By managing the vertices in each connected component in a data structure that supports fast (e.g. \(O(\log N)\)) retrieval of the \(k\)-th largest value, together with the merging technique, it can be solved in \(O(N\log^2 N+Q\log N)\) time.

\(O((N+Q)\log N)\) solution

When you construct a tree that represents the process of mergers in the DSU (Disjoint Set Union), the query is rephrased to: “what is the \(k\)-th largest vertex in the subtree rooted at vertex \(u\)?” This is nothing but Subtree K-th Max; as in a user editorial of this problem, one can perform an Euler tour to correspond subtrees to segments, and use a Wavelet Matrix to solve it in a total of \(O((N+Q)\log N)\) time.