結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
|
提出日時 | 2025-07-22 17:49:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,603 ms / 3,000 ms |
コード長 | 3,096 bytes |
コンパイル時間 | 782 ms |
コンパイル使用メモリ | 82,248 KB |
実行使用メモリ | 400,936 KB |
最終ジャッジ日時 | 2025-07-22 17:49:27 |
合計ジャッジ時間 | 13,632 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
# Generated By Gemini 2.5 pro import sys # 再帰回数の上限を増やす sys.setrecursionlimit(2 * 10**5 + 5) def solve(): """ 問題を解くメインの関数 """ try: N_str = sys.stdin.readline() if not N_str: return N = int(N_str) except (IOError, ValueError): return adj = [[] for _ in range(N)] for _ in range(N - 1): u, v = map(int, sys.stdin.readline().split()) u -= 1 v -= 1 adj[u].append(v) adj[v].append(u) # N=2 の場合は答えが2で確定 if N == 2: print(2) return # down_max1[u]: uの部分木内でのuからの最大深さ # down_max2[u]: uの部分木内でのuからの2番目の最大深さ down_max1 = [0] * N down_max2 = [0] * N # ステップ1: 子から親へのDFS def dfs1(u, p): max1, max2 = 0, 0 for v in adj[u]: if v == p: continue dfs1(v, u) dist = down_max1[v] + 1 if dist > max1: max2 = max1 max1 = dist elif dist > max2: max2 = dist down_max1[u] = max1 down_max2[u] = max2 # 頂点0を根としてdfs1を実行 dfs1(0, -1) # 最終的な答え ans = 1 # ステップ2: 親から子へのDFS(全方位木DP) def dfs2(u, p, up_dist): nonlocal ans # uを根としたときの、各枝の最大深さのリストを作成 branch_dists = [up_dist] for v in adj[u]: if v == p: continue branch_dists.append(down_max1[v] + 1) # 降順にソート branch_dists.sort(reverse=True) # uを中心としたウニ木の最大サイズを計算 current_max_size_contrib = 0 for i, d in enumerate(branch_dists): # i+1 が枝の本数 k に対応 current_max_size_contrib = max(current_max_size_contrib, d * (i + 1)) ans = max(ans, 1 + current_max_size_contrib) # 子に渡す up_dist を計算して再帰呼び出し for v in adj[u]: if v == p: continue # uから見てv方向の枝の深さ dist_from_v = down_max1[v] + 1 # uから見てv以外の方向の枝の最大深さ parent_side_max_dist = up_dist if dist_from_v == down_max1[u]: # v方向が最も深い枝だったので、2番目の深さを使う parent_side_max_dist = max(parent_side_max_dist, down_max2[u]) else: # v方向以外に最も深い枝があるので、それを使う parent_side_max_dist = max(parent_side_max_dist, down_max1[u]) # vに渡すup_distは、uからの距離なので+1する dfs2(v, u, parent_side_max_dist + 1) # 頂点0、親-1、親方向の距離0でdfs2を開始 dfs2(0, -1, 0) print(ans) solve()