典型データ構造で解きます。

根付き木の各部分木を \(1\) つの区間に対応させる方法を知っていますか？　オイラーツアーです。この問題は、長さ \(N\) の数列 \(X\) に対して次のクエリを処理する問題に変形できます。

\(l\) , \(r\) , \(k\) が与えられます。 \((X _ l , X _ {l+1} , \ldots , X _ {r-1} )\) のうち \(k\) 番目に大きい値を出力してください。

これは Library Checker の “Range Kth Smallest” ( https://judge.yosupo.jp/problem/range_kth_smallest ) そのものです。座標圧縮と Wavelet Matrix のクエリ \(\text{quantile}\) を用いて計算量 \(O( (Q+N) \log N)\) を達成できます。

解答例 (C++ (GCC 9.2.1) , 122 ms) （ main 関数はかなり下にあります）