GRL_5_A: Diameter of a Tree

関節点の問題はいっこうにやり方が降りてこないし
ここんとこどれもそんな感じなので
わからないものはいったん放置して先へ進むことに

今回は木の直径
まずは雑に端から端までの距離を全部求めていこう
この問題はそこから改良していけそうな気がする

class Node():
    def __init__(self, key):
        self.key = key
        self.indeg = 0
        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].indeg += 1
        T[t].indeg += 1
        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 = 0
    S = []
    S.append((s, 0))

    while S != []:
        v, vr = S.pop()
        v.passed = True
        is_end = True
        for a, w in v.adj:
            if not a.passed:
                S.append((a, vr + w))
                is_end = False
        if is_end:
            fur = max(fur, vr)

    return fur

def tree_diameter(T):
    r = 0
    for s in T:
        if s.indeg == 1:
            r = max(r, furthest(T, s))
    return r

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

if __name__ == "__main__":
    main()

Case #22 (頂点数1000)は0.50sで通過
Case #23 (頂点数5000)でTLE