Atcoder典型90問 003 - Longest Circular Road（★4）
▶︎https://atcoder.jp/contests/typical90/tasks/typical90_c
問題
N 個の都市があり、それぞれの都市に 1 から N までの番号が付けられています。
また、N−1 本の道路があり、
i 本目 (1≤i≤N−1) の道路は都市Aiと都市Biを双方向に結んでいます。 どの都市の間も、いくつかの道路を通って移動可能なものとなっています。
さて、あなたは整数 u, v (1≤u<v≤N) を自由に選び、都市 u と都市 v を双方向に結ぶ道路を
1 本だけ新設することができます。そこで、以下で定められる値を スコア とします。
同じ道を2 度通らずにある都市から同じ都市に戻ってくる経路における、通った道の本数
（この値はただ 1 つに定まる）
スコアとして考えられる最大の値を出力してください。
制約
3 \leq N \leq 100000
都市同士は連結グラフをなす
試したこと & 適切な方針
- 調べつつ解けた、嬉しい
- 一筆書きなので深さ優先探索っぽいが...？
- N個の都市にN-1本の道路、全ての頂点は互いに到達可能(連結グラフ) というかなり厳しい条件をうまく使いたい。
- これは閉路が存在しないのでは？→木構造説
- 木構造であること(グラフ内に閉路が存在しないこと)の証明
グラフの頂点集合を \mathbb{V} 、道の集合を \mathbb{E}と定める。\\
閉路の集合 \mathbb{L}と \exists L \in \mathbb{L} について、\\
閉路Lを構成している頂点の集合\mathbb{V}_{in} と \mathbb{V}_{out} = \bar{\mathbb{V}_{in}}を定める。\\
以下の操作を定義する。\\
- \\
* ∃V \in \mathbb{V}_{out} について、\mathbb{V}_{in} = \mathbb{V}_{in} \cup V と更新し、\mathbb{V}_{out} = \mathbb{V}_{out} \backslash V と更新する\\ - \\
以上の操作は、閉路LからLに所属していない頂点に辺を伸ばす操作と一致する。\\
ここで、\mathbb{V}_{in}を構成する頂点集合の要素数をkとすると、Lを構成する辺は最低でもk本存在する。\\
そのため、グラフ\mathbb{G} = {\mathbb{V}, \mathbb{E}}を連結グラフとするためにはのこり N-k-1本の\\
辺を用いて 操作(*)をN-k-1回行い、その結果として\mathbb{V}_{out}の要素であるようなN - k個の頂点を全て\\
\mathbb{V}_{in}に加える必要があるが、これは操作の性質上不可能である。よって、Gに閉路は存在しない。
- 以上の分析から、この問題で与えられるグラフは閉路のない連結グラフ、すなわち木構造グラフであり、その木構造に一本足してなるべく長い唯一の閉路を作れ、という問題に帰着する。
- 以上の考察を踏まえると、「辺を追加して最も長い閉路を作る」という行為は、「グラフの中で最も遠まわりのできる二点をつないでいる、一番長い"道"の始点と終点をつなぐ」行為と同一である(木構造のうち最も長い道の始点を最も高い頂点とした木構造グラフを考えれば自明である)
- 閉路がないので、ある点から別の点までに到達する道が一意に定まる。やっぱり木構造は強い性質をもってるなあという印象。
- 上は木の直径を求める操作であり、O(N)で解決する。
- 到達距離の話になるので、やっぱり幅優先探索だとわかる。
解説付きコード
from collections import deque
#幅優先探索の実装
def bfs(s, N, elist):
#探索対象の点をqueueに格納していく
queue = deque([s])
#distはi番目の点までの距離、-1は未探索
dist = [-1 for i in range(N)]
dist[s] = 0
#探索対象の点が無くなるまで実行
while queue:
v = queue.popleft()
for i in elist[v]:
#iが未探索の場合、距離を更新し探索対象に新たに加える
if dist[i] < 0:
dist[i] = dist[v] + 1
queue.append(i)
return dist
N = int(input())
elist = [[] for i in range(N)]
for i in range(N-1):
[a, b] = list(map(int, input().split()))
a -= 1
b -= 1
elist[a].append(b)
#無向グラフであることに注意
elist[b].append(a)
dist = bfs(0, N, elist)
longs = dist.index(max(dist))
longestdist = max(bfs(longs, N, elist))
print(longestdist + 1)