競プロ典型90問 003 - Longest Circular Road

問題

競プロ典型90問　003 - Longest Circular Road

考察

スコアの最大値とは

スコアは2都市間の距離+1となります。
つまり、スコアの最大値を求めるには2都市間の距離の最大値を求めれば良い。

2都市間の最長の距離を求めるためにどうすれば良いか

今回、N都市間にN-1本の道路があるので各都市間の行き方は1通りしかありません。よって、
最長距離になる2都市をA_q,B_qとすると、任意の都市から最も遠い都市はA_q,B_qのどちらかになります。

そこで、A_qとB_qの間の距離を求めるために
まず、ある任意の都市から1番遠い都市を求めます。(これがA_qかB_qのどちらか)
そこから一番遠い都市との距離を求めればそれが2都市間の最長距離になります。

ではある都市からの最長距離をどのように求めるか

ここは全然わからなかったのでググりました。
BFS(幅優先探索)やDFS(深さ優先探索)というものがあるらしいです。
幅優先探索は最短距離を調べるのに良いみたいです。とりあえず今回は深さ優先探索を使ってみました。
深さ優先探索は先に行けるところまで探索して行けるところがなくなると一歩戻って探索するというようなアルゴリズムです。

ソース

都市の番号ごとに繋がる都市を配列に読み込みます。
そして、都市1から一番遠い都市を探し出し、その都市から一番遠い都市との距離を求めます。

import sys
sys.setrecursionlimit(10**7)

N  = int(input())

connect = [[] for i in range (N+1)]

for i in range(N-1):
    A,B = map(int,input().split())
    connect[A].append(B)
    connect[B].append(A)

distance = [0] * (N+1)
def dfs(now,pre,dist):
    distance[now] = dist
    for i in connect[now]:
        if i != pre:
            dfs(i,now,dist+1)
dfs(1,-1,0)
maxdis = max(distance) 
for i in range(len(distance)):
    if distance[i] == maxdis:
        workCity = i
        break

distance = [0] * (N+1)
dfs(workCity,-1,0)

print(max(distance)+1)

もう少し処理をまとめて、都市の番号だけ渡すような関数を作ったらよかったかなと思いました。

あと、最初の提出で下の処理を

maxdis = max(distance) 
for i in range(len(distance)):
    if distance[i] == maxdis:
        workCity = i
        break

下のように書いてしまい、TLEをくらいました。
解説読んでも方針合っててDFS使うのも合ってるし、なんでだ？とめちゃくちゃ混乱しました。こういうミスは減らしていかないとですね。

for i in range(len(distance)):
    if distance[i] == max(distance):
        workCity = i
        break

最後に

どうやって最長の2都市を探すかという方針は割と早めに立ったのですが、DFS等の探索するアルゴリズムを知らなかったため、ある都市からの距離を求めるという工程の実装にかなり時間がかかってしまいました。
とはいえ、あれこれ考えていたけどとりあえずDFSのコードの例を探してきて同じように書いてみればすぐACすることができたのであれこれ考える前に方針が立ったらコードを書いてみないとなと思いました。

相変わらずアルゴリズムの知識不足と実装力不足が課題ですが、競プロ典型90問をやることで解消していけないかなと思っています。

以上、最後まで読んでいただきありがとうございました。