結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2025-07-20 00:58:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 518 ms / 3,000 ms
コード長 1,466 bytes
コンパイル時間 319 ms
コンパイル使用メモリ 82,672 KB
実行使用メモリ 122,392 KB
最終ジャッジ日時 2025-07-20 00:58:41
合計ジャッジ時間 9,423 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin

#重みのないグラフでの最短経路問題
#隣接リストと始点を与えると始点からの距離のリスト & 親のリストを返す
from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]
    visit = []

    while len(q) > 0:
        now = q.popleft()
        visit.append(now)

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis,visit

N = int(stdin.readline())

lis = [ [] for i in range(N)]

for i in range(N-1):
    u,v = map(int,stdin.readline().split())
    u -= 1
    v -= 1
    lis[u].append(v)
    lis[v].append(u)

_,plis,visit = NC_Dij(lis,0)
visit.reverse()


dpc = [1] * N

for v in visit:
    if plis[v] != v:
        dpc[plis[v]] = max(dpc[plis[v]], dpc[v] + 1)

ans = 1
visit.reverse()
dpu = [0] * N

for v in visit:

    links = [ dpu[v] ]

    for nex in lis[v]:
        if nex == plis[v]:
            continue
        links.append( dpc[nex] )

    links.sort()
    links.reverse()

    for i in range(len(links)):
        ans = max(ans, 1+(i+1)*links[i])

    for nex in lis[v]:
        if nex == plis[v]:
            continue
        cost = (links[0] if links[0]!=dpc[nex] else links[1]) + 1
        dpu[nex] = cost

print (ans)
0