GRL_5_A: Diameter of a Tree (続き2)

頂点数100000をクリアするには始点でループしてる場合じゃない気がしてきた

いったん戻って考えよう

ヒントの絵でをよく見ると、端の頂点から反対側の頂点に探索したあと、
そこから戻るようにしてまた別の端へ探索しているように描いてある
これはどういう意味か

とりあえず最初は適当な葉からはじめて、一番遠い葉を探したら
そこからまた一番遠い葉を探す、を繰り返せってことかな
確かに全部の葉を順番に探すよりも効率はよさそうだ
ニュートン法みたい

でも、どうなったら終わりにしていいんだ？
全部の歯を試すようなことにはならないだろうし
行って戻って同じところに戻ってきたら、とか？
極小値にはまりこむみたいなことはないのかな？
最小であるという保証はある？
まあやってみるか

探索は幅優先に戻そう
昨日書いた深さ優先だと短いのはいいけど一番遠い頂点が出てこない
（深さ優先でも出せる書き方はと思うけど）

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
    fur_v = None
    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 and vr > fur:
            fur = vr
            fur_v = v

    return fur, fur_v

def tree_diameter(T):
    if len(T) == 1:
        return 0

    s = [s for s in T if s.indeg == 1][0]
    prev = None
    while True:
        fur, fur_v = furthest(T, s)
        if fur_v is prev:
            return fur
        prev = s
        s = fur_v

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

if __name__ == "__main__":
    main()

よしAC

何回くらいで収束するのかな
いくつか試す
3回
3回
3回

・・・これは？
もしや？
行って戻るだけでいいと言ってるの？
（3回目は同じ経路を戻るだけ）

def tree_diameter(T):
    if len(T) == 1:
        return 0

    s = [s for s in T if s.indeg == 1][0]
    fur, s2 = furthest(T, s)
    fur, fur_v = furthest(T, s2)

    return fur

AC
mjsk

行って戻るくらいでも相当いい近似になるとは思ったけど
解説だ解説