結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
コンテスト
ユーザー kidodesu
提出日時 2025-07-18 21:59:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 941 ms / 3,000 ms
コード長 1,758 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 148,816 KB
最終ジャッジ日時 2025-07-18 21:59:34
合計ジャッジ時間 12,958 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
node = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = [int(x)-1 for x in input().split()]
    node[u].append(v)
    node[v].append(u)

from collections import deque
def basic_tree(s = 0):
    D = [-1 for _ in range(n)] #深さ
    DD = [[] for _ in range(n)] #深さごとの要素
    C = [1 for _ in range(n)] #根付き木の要素数
    D[s] = 0
    dq = deque([s])
    while dq:
        now = dq.popleft()
        DD[D[now]].append(now)
        for nxt in node[now]:
            if D[nxt] == -1:
                D[nxt] = D[now] + 1
                dq.append(nxt)
    for i in range(n-1, 0, -1):
        for now in DD[i]:
            for nxt in node[now]:
                if D[nxt] == D[now] - 1:
                    C[nxt] += C[now]
    return D, DD, C

D, DD, C = basic_tree()


A = [0] * n
B = [0] * n
dp = [[] for _ in range(n)]
for d in DD[::-1]:
    for now in d:
        for nxt in node[now]:
            if D[nxt] < D[now]:
                continue
            a = A[nxt]+1
            if A[now] < a:
                A[now], B[now] = a, A[now]
            elif B[now] < a:
                B[now] = a
            dp[now].append(A[nxt]+1)

ans = 0
for d in DD:
    for now in d:
        for nxt in node[now]:
            if D[nxt] > D[now]:
                continue
            if A[nxt] == A[now]+1:
                a = B[nxt]+1
            else:
                a = A[nxt]+1
            if A[now] < a:
                A[now], B[now] = a, A[now]
            elif B[now] < a:
                B[now] = a
            dp[now].append(a)
        dp[now].sort(reverse = True)
        ma = 1 << 30
        for i in range(len(dp[now])):
            ma = min(ma, dp[now][i])
            ans = max(ans, 1 + (i + 1) * ma)

print(ans)
0