森に対して

• \(u,v\) 間に辺を張る（森を保つ操作のみ行える）
• \(u,v\) が同じ連結成分にあるかを調べる．同じ成分にある場合，\(u\) から \(v\) 方向に辺 \(k\) 個分進む

といった操作は Link Cut Tree というデータ構造を用いて行える基本的な操作です．（Link：辺を張る操作のほかに，Cut：辺の削除も行えます）

したがって本問は Link Cut Tree を使えばすぐに解ける問題です．

Link Cut Tree は比較的実装が大変なデータ構造だということもあって，AtCoder 公式コンテストの想定解法になったことは私が知る限りありません（海外コンテスト等ではしばしば見かけます）が，興味があれば学んでみてください．

日本語文献では，

• プログラミングコンテストでのデータ構造 2 ～動的木辺～ , iwiwi さん
• かつっぱの木マスター養成講座, catupper さん
• ei1333の日記, Link-Cut 木, ei1333さん
• ei1333の日記, QTREE LCT + Dynamic Distance Sum, ei1333さん, いろいろな応用例の紹介

などが有名だと思います．いろいろな実装例を見たい場合には，Library Checker の Dynamic Tree シリーズ（例）の提出などから探してみてください．