Codeforces 519E

問題

N頂点からなる、辺の重みが1の連結な木が与えられる。
M個のA,Bが与えられ、「頂点AとBから同じ距離に位置する頂点の個数」をそれぞれ返す。

N<=10^5
M<=10^5

考え方

任意の木では、個数の数え上げが難しいので、頂点1をルートとする根付き木にしておく。
考察すると、A、Bからの距離が同じで、かつ、距離の合計が最小となる頂点を求められれば、その頂点から出ているA,B頂点方向にのびる辺ではない辺を辿っていける頂点はすべて同じ距離になる。

まず、A,Bの深さの偶奇があっていなければ距離の中間にあたるノードが存在しないので、0を返してよい。そうでなければかならず1つ以上のノードが存在する。
また、A=Bの場合は、すべての頂点の距離が等しくなるので、Nを返してよい。

Aの深さとBの深さが同じ場合は、LCAを求めると、その頂点が距離が同じで最小距離の頂点になる。
木DPで、その頂点以下の部分木の頂点数を計算しておけば、LCAに隣接するA方向へのびる頂点をA'、B方向へのびる頂点をB'とすると、N-dp[A']-dp[B']が答えになる。

Aの深さとBの深さが異なる場合は、距離が同じで最小距離となる頂点の深さは、depth=(Aの深さ-LCAの深さ + Bの深さ-LCAの深さ)/2になる。
Aの方が深い場合は、AからLCAの間で、深さがdepthとdepth+1となる頂点v,v'を探すことで、答えはdp[v]-dp[v']で求められる。
深さがdepthとなる頂点vを求めるのは、O(logN)でのLCAを求める時と同様に求められる。

LCA前処理でO(NlogN)で、クエリ処理部分がO(MlogN)になるので、間に合う。