結果

問題 No.806 木を道に
ユーザー 双六双六
提出日時 2019-04-06 07:43:56
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,687 bytes
コンパイル時間 102 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 68,344 KB
最終ジャッジ日時 2024-06-23 12:38:33
合計ジャッジ時間 12,564 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
11,008 KB
testcase_01 AC 30 ms
11,136 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 30 ms
11,136 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 31 ms
11,008 KB
testcase_08 AC 32 ms
11,136 KB
testcase_09 AC 31 ms
11,136 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 376 ms
39,016 KB
testcase_25 AC 561 ms
44,564 KB
testcase_26 AC 286 ms
26,416 KB
testcase_27 AC 934 ms
68,344 KB
testcase_28 AC 52 ms
12,416 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