GRL_5_A: Diameter of a Tree (続き)

ヒントが幅優先探索だったから幅優先で書いたけど
このレベルだと別に深さ優先でも同じだなあ

と思って深さ優先で書いてみたらリスト閉包で書けてずっと短くなった

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

    def rec(v):
        v.passed = True
        return max([0] + [rec(a) + w for a, w in v.adj
                          if not a.passed])

    return rec(s)

と言ってもACに近付いたというわけではない
少し遅くなったし

この形ならメモ化できるかな
といってもrec(v)をそのままメモ化することはできなさそうなので
少々無理して・・・

cache = {}

def furthest(T, s):

    def rec(v):
        v.passed = True
        fur = 0
        for a, w in v.adj:
            if not a.passed:
                if (v, a) in cache:
                    d = cache[(v, a)]
                else:
                    d = rec(a) + w
                    cache[(v, a)] = d
                fur = max(fur, d)
        return fur

    for v in T:
        v.passed = False
    return rec(s)

Case #23、#24は通過して#25(頂点数20000)でTLE
頂点数100000をクリアするには始点でループしてる場合じゃない気がしてきた