各頂点の深さを前計算しておくことで、次のクエリに高速に答えることができれば良くなります。

頂点 \(x\) と整数 \(k\) が与えられるので、\(x\) から親方向への辺を \(k\) 回辿った先にある頂点を答えよ。

これは Level Ancestor と呼ばれる問題です。

例えばダブリングを用いれば、前計算 \(O(N \log N)\) 時間、\(1\) クエリあたり \(O(\log N)\) 時間で処理できます。やや高度ですが、Heavy-Light Decomposition を用いると前計算 \(O(N)\) 時間、各クエリ \(O(\log N)\) 時間にできます。

オフラインで \(O(N+Q)\) 時間で処理する方法も知られています。なお、高度なアルゴリズムを用いてオンラインで \(O(N+Q)\) 時間にすることも可能です。