GRL_5_A: Diameter of a Tree (続き3)

解説だ解説

行って帰るだけでいいんだよっていう説明があった
そうならざるを得ないことはわかった
そうなりそうだという感覚は残念ながらない

d(u, v)≧d(x, y)をわざわざ示してるところがあるけど
uvが直径なんだから仮定よりそうなります、じゃだめなのかなあ

しかも、最初に始める点はどこでもいいのか
若干図に騙された気がしないでもない
そういうとことか模範解答とか見ながらコードを整理

from collections import deque

class Node():
    def __init__(self, key):
        self.key = key
        self.passed = False
        self.adj = []

def read_inputs():
    n = int(input())
    T = [Node(i) for i in range(n)]
    for _ in range(n - 1):
        s, t, w = [int(x) for x in input().split()]
        T[s].adj.append((T[t], w))
        T[t].adj.append((T[s], w))
    return T

def furthest(T, s):
    for v in T:
        v.passed = False

    fur = -1
    fur_v = None
    Q = deque()
    Q.append((s, 0))

    while len(Q) > 0:
        v, vr = Q.popleft()
        if vr > fur:
            fur = vr
            fur_v = v
        v.passed = True
        for a, w in v.adj:
            if not a.passed:
                Q.append((a, vr + w))

    return fur, fur_v

def tree_diameter(T):
    _, s = furthest(T, T[0])
    fur, _ = furthest(T, s)
    return fur

def main():
    T = read_inputs()
    r = tree_diameter(T)
    print(r)

if __name__ == "__main__":
    main()

最大のやらかしは幅優先といいつつキューではなくてスタックを使ってたこと
前にもやったような気がする
結果は変わらないけど