結果

問題 No.806 木を道に
ユーザー LyricalMaestro
提出日時 2025-04-12 16:20:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,017 bytes
コンパイル時間 451 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 90,972 KB
最終ジャッジ日時 2025-04-12 16:20:22
合計ジャッジ時間 5,536 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/806

from collections import deque

MAX_INT = 10 ** 18


def dijkstra(N, next_nodes, start):
    dists = [MAX_INT] * N
    queue = deque()

    dists[start] = 0
    queue.append(start)
    while len(queue) > 0:
        v = queue.popleft()

        for w in next_nodes[v]:
            if dists[w] == MAX_INT:
                dists[w] = dists[v] + 1
                queue.append(w)
    return dists

def main():
    N = int(input())
    next_nodes = [[] for _ in range(N)]
    for _ in range(N -  1):
        a, b  = map(int ,input().split())
        next_nodes[a - 1].append(b - 1)
        next_nodes[b - 1].append(a - 1)
    
    dists = dijkstra(N, next_nodes, 0)

    target_i = -1
    target_dist = -1
    for i in range(N):
        if target_dist < dists[i]:
            target_dist = dists[i]
            target_i = i

    dists = dijkstra(N, next_nodes, target_i)

    diag = max(dists)
    print(N - (diag + 1))




                




if __name__ == "__main__":
    main()
0