ABC 209 D - Collisionの解説
問題概要
N個の町がN-1本の道路でつながっており、街には1からNの番号が付いている。道路を通ってどの町からどの町へも移動できる。また道路はすべて同じ長さである。
Q個のクエリが与えられて、各クエリでは町の番号c, dが与えられる。cとdを同時に二人の人が出発し、二人とも同じ速さで最短経路を通ってもう一方の町に向かう。この時、二人の人が出会うのは町で出会うか道路上で出会うか判定せよ。
制約
2 ≦ N ≦ 10^5
1 ≦ Q ≦ 10^5
問題の解法
最初に考えるポイントは二つあります。
- N個の町がN-1本の道路でどの町からどの町へも移動できるということは、町と道が木構造のグラフになっている。したがって2つの町の間の最短経路は一意に定まる。
- 町c, d間の距離が偶数ならば二人は町で出会う。奇数ならば道路上で出会う。
このことによって、町と道からなる木構造のグラフ上で、任意の2頂点間の距離の偶奇がわかればよいことになります。
もちろんクエリのたびに距離をBFSなどで求めていては計算量がO(NQ)になってしまい、間に合いません。どのようにすれば効率化できるでしょうか? 以下のように絵を描きながら考えてみると、ノードの深さを利用すればうまく行くことがわかります。
下の図のような構造の木を例にとって考えてみましょう。
町Aと町Bの間の距離は、二つの町が根を介して反対側にあるので、根からの深さの和と等しくなり、5になることがわかると思います。このことから、ノードの深さが役に立ちそうということが示唆されます。
次に、下のように町Aと町Cの場合について考えてみましょう。町Aと町Cは町Dを経由して最短距離は3になります。この場合はAとCの深さの和5は最短距離とは等しくなりません。
しかし町A → 町D → 町Cという最短経路と、町A→根→町Cという経路(この場合の距離はA, Cの深さの和)で違う点は、下図の赤い矢印の部分だけになります。この赤い矢印の部分はDと根の間を往復しているので、どのような場合でも赤い矢印の距離の合計は偶数になります。
したがって、(AからCへの最短距離)と(AとCの深さの和)の違いは必ず偶数になり、この二つ数の偶奇は一致します。
この性質は一般的な木構造のグラフの任意の2頂点間で成立し、いわゆるLCAをこの図でいうDとして考察をすれば同じ結果になります。もちろん、A, Cの深さだけがわかれば偶奇の判定ができるので、LCAを陽に求める必要はありません。*1
以上の考察から、元の問題は二つの頂点の深さの和を計算して、偶数ならば町、奇数ならば道となることになります。*2
したがって、適当な頂点を根とした木を作って、各ノードの深さを先に計算しておけば、各クエリに対してO(1)で回答をすることができます。
提出コード
Submission #24149505 - AtCoder Beginner Contest 209
from collections import deque def main(): [N, Q] = [int(x) for x in input().split()] # グラフの初期化 graph = [[] for _ in range(N+1)] for _ in range(N-1): [a, b] = [int(x) for x in input().split()] graph[a].append(b) graph[b].append(a) # 深さを記録するリスト depth_vec = [-1 for _ in range(N+1)] # 1を根とする根付き木を作り、各頂点の深さを記録する queue = deque() queue.append((1, 0)) while len(queue) > 0: (node, depth) = queue.pop() depth_vec[node] = depth for child in graph[node]: if depth_vec[child] >= 0: continue queue.append((child, depth+1)) # クエリに解答する for query in range(Q): [c, d] = [int(x) for x in input().split()] if (depth_vec[c] + depth_vec[d]) % 2 == 0: print("Town") else: print("Road") if __name__ == "__main__": main()
