提出 #32438989

---

ソースコード 拡げる

def main(N, AB):
    dp = dict()
    def route(a, b, wrongway=None):
        '''aからbまでに通る道の数を返す
        
        wrongwayからaに移動したことを示す。
        '''
        if (a, b, wrongway) in dp:
            return dp[(a, b, wrongway)]
        
        if b in net[a]:
            ret = 1
        else:
            if wrongway is not None:
                available = net[a].copy()
                available.remove(wrongway)
            else:
                available = net[a]
                
            for way in available:
                ret = 1 + route(way, b, a)
                if ret != 0:
                    break
            else:
                ret = -1
        
        dp[(a, b, wrongway)] = ret
        return ret
        
        
    
    # 各都市から見て繋がっている都市のリスト
    net = {i: list() for i in range(1, N+1)}
    
    for a, b in AB:
        net[a].append(b)
        net[b].append(a)
    # print(net)
    # 末端の都市を抽出
    terminals = [k for k, v in net.items() if len(v) == 1]
    
    # 1つの末端から、最大経路の末端を探す
    one_end = None
    w_routes = 0
    for term in terminals[1:]:
        r = route(terminals[0], term)
        if r > w_routes:
            w_routes = r
            one_end = term
        
    # 見つけた末端から最大経路の末端を探す
    terminals.remove(one_end)
    return max([route(one_end, term) for term in terminals]) + 1
 
N = int(input())
AB = [list(map(int, input().split(" "))) for _ in range(N-1)]
print(main(N, AB))

提出情報

ジャッジ結果