No.070 D

頂点 $K$ を根とする根付き木と考える. そして各頂点ごとに根までの移動距離を求めておく. 根までの移動距離は, (その頂点と親との距離) + (親から根までの移動距離) で求められるので, 根から順に幅優先探索で計算していけば $O(N)$ で計算できる.

各クエリにおいては, $x_i$ から根までの移動距離と $y_i$ から根までの移動距離の和を出力する. 各頂点から根までの移動距離は計算済なので, クエリごとの計算量は $O(1)$ である.

よってすべての計算量は $O(N+Q)$ となり, 十分間に合う.