結果

問題 No.806 木を道に
ユーザー 双六双六
提出日時 2019-04-06 07:43:56
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,687 bytes
コンパイル時間 766 ms
コンパイル使用メモリ 10,840 KB
実行使用メモリ 63,300 KB
最終ジャッジ日時 2023-09-05 17:07:45
合計ジャッジ時間 11,808 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 20 ms
8,804 KB
testcase_01 AC 19 ms
8,852 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 19 ms
8,672 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 19 ms
8,764 KB
testcase_08 AC 21 ms
8,872 KB
testcase_09 AC 19 ms
8,832 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 318 ms
35,240 KB
testcase_25 AC 457 ms
41,656 KB
testcase_26 AC 233 ms
24,548 KB
testcase_27 AC 768 ms
62,964 KB
testcase_28 AC 39 ms
10,268 KB
権限があれば一括ダウンロードができます

ソースコード

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