結果

問題 No.806 木を道に
コンテスト
ユーザー 双六
提出日時 2019-04-06 07:43:56
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,687 bytes
コンパイル時間 102 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 68,344 KB
最終ジャッジ日時 2024-06-23 12:38:33
合計ジャッジ時間 12,564 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()


class breadth(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0
        self.visit = ["no" for i in range(len(graph) + 1)]
        self.visit[s] = "yes"
        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[s], s))

        while self.Q:
            dist_u, u = heappop(self.Q)
            for v in self.g[u]:
                if self.visit[v] == "yes":
                    continue
                else:
                    self.dist[v] = dist_u + 1
                    self.prev[v] = u
                    self.visit[v] = "yes"
                    heappush(self.Q, (self.dist[v], v))

    def s_d(self, goal):
        return self.dist[goal]

    def s_p(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

N = int(input())
g_a = Graph()
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    g_a.add_edge(a, b)
    g_a.add_edge(b, a)

s = 1
E = breadth(g_a, s)
x = 0
for i in E.dist:
    if E.dist[i] > x:
        x = E.dist[i]
        y = i

F = breadth(g_a, y)
x = 0
for i in F.dist:
    if F.dist[i] > x:
        x = F.dist[i]
        y = i

print(N - 1 - x)
0