問題
003 - Longest Circular Road（★4）
ポイント
この問題で与えられているデータは木構造をしています。
※木構造のデータについて、詳細を知りたい方は下記記事が参考になると思います。
ITの基礎知識｜ITパスポート・基本情報 - 木構造
「同じ道を2度通らずにある都市から同じ都市に戻ってくる経路における、通った道の本数」を
最大にするには、
①木の直径を求める
②木の直径となっている都市 u と都市 v を双方向に結ぶ道路を 1 本新設する
③木の直径+1を答えとして出力する
といった手順を踏めば良いです。
木の直径の求め方ですが、はじめにどこの都市からでも良いので深さ優先探索（BFS）を行い、
その後最も遠かった都市から再度BFSを行うと求めることができます。
※BFSについては下記記事の解説が分かりやすいです。いずれこのブログでも解説記事書きます！
【AtCoder】Pythonで使いこなす深さ優先探索・幅優先探索
何故そうなるのかを簡単に説明します。
※数学的証明とは程遠いのですが、何となくイメージだけでも掴んでいただければと！
以下の都市u,vが直径を成している木を考えます。
そこで、ある都市xからBFSをし、一番遠い都市 v にたどり着きました。
その後、都市vからBFSを行うと直径の端である都市uにたどり着くという寸法です。
以上を踏まえ、実装したコードがこちらです。
コード
def main():
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
a, b = map(int, input().split())
edges[a].append(b)
edges[b].append(a)
dist = [0] * (N+1)
def dfs(x, last):
for to in edges[x]:
if to == last:
continue
dist[to] = dist[x] + 1
dfs(to, x)
dfs(1, -1) # スタートは何でも良いのでdfs1回目
max_dist = max(dist)
max_dist_node = dist.index(max_dist)
# dfs2回目
dist = [0] * (N+1)
dfs(max_dist_node, -1)
print(max(dist) + 1) # 直径 + 1 を出力
if __name__ == '__main__':
main()
