クエリにおける \(K_i\) の最大値を \(K\) と表します。

「 \(i\) の部分木に含まれる頂点に書かれた整数のうち、大きい方から順に \(K\) 個が入った配列」を \(P_i\) とします。 予め全ての \(i\) に対して \(P_i\) を求めておくことができればクエリには \(O(1)\) で答えることができます。

\(P\) を葉から順に求めることを考えます。ある頂点 \(i\) の子たち \(j_1,\ldots,j_{m_i}\) のすべてについて \(P\) が求まっていると仮定します。このとき、\(P_{j_1},\ldots,P_{j_{m_i}}\) をまとめてソートし、大きい方 \(K\) 個の値からなる配列が \(P_i\) になります。したがって、\(\sum_i O(m_i K\log (m_i K))=O(NK\log(NK))\) 時間で全ての頂点に対して \(P\) を求めることができました。