提出 #25848703

---

ソースコード 拡げる

# -*- coding: utf-8 -*-
"""
003 - Longest Circular Road（★4）
https://atcoder.jp/contests/typical90/tasks/typical90_c

"""
import sys
from heapq import heappush, heappop


def dijkstra(adj, s):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * len(adj)
    d = [float('inf')] * len(adj)
    d[s] = 0
    pq = []
    heappush(pq, (0, s))
    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue
        for v, cost in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + cost:
                d[v] = d[u] + cost
                heappush(pq, (d[v], v))
                color[v] = GRAY
    return d


def solve(N):
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a].append((b, 1))
        adj[b].append((a, 1))
    dist = dijkstra(adj, 1)
    max_dist = max(dist[1:])
    dist = dijkstra(adj, dist.index(max_dist))
    return max(dist[1:]) + 1


def main(args):
    N = int(input())
    ans = solve(N)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

提出情報

ジャッジ結果