Let \(K\) be the maximum value of \(K_i\) in the queries.

Let \(P_i\) be an array containing “\(K\) largest integers among the integers written on the vertices included in the subtree rooted at \(i\).” By precalculating \(P_i\) for every \(i\), the query can be answer in an \(O(1)\) time each.

Consider finding \(P\) from the leaves. For a vertex \(i\), suppose that \(P\) has already been found for all children \(j_1,\ldots,j_{m_i}\) of \(i\). Then, sort \(P_{j_1},\ldots,P_{j_{m_i}}\) at once, then \(P_i\) is an array consisting of the \(K\) largest values of the sorted array. Therefore, \(P\) has been found for all vertex in a total of \(\sum_i O(m_i K\log (m_i K))=O(NK\log(NK))\) time.