結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
![]() |
提出日時 | 2025-07-18 21:49:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,089 ms / 3,000 ms |
コード長 | 1,788 bytes |
コンパイル時間 | 258 ms |
コンパイル使用メモリ | 82,592 KB |
実行使用メモリ | 295,424 KB |
最終ジャッジ日時 | 2025-07-18 21:49:20 |
合計ジャッジ時間 | 15,363 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
from types import GeneratorType def bootstrap(f, stack=[]): def wrappedfunc(*args, **kwargs): if stack: return f(*args, **kwargs) to = f(*args, **kwargs) while True: if type(to) is GeneratorType: stack.append(to) to = next(to) else: stack.pop() if not stack: break to = stack[-1].send(to) return to return wrappedfunc N = int(input()) G = [[] for _ in range(N)] for _ in range(N-1): u, v = map(int, input().split()) u, v = u-1, v-1 G[u].append(v) G[v].append(u) @bootstrap def dfs(n, p): MAX = 0 for i, v in enumerate(G[n]): if v == p: continue dp[n][i] = yield dfs(v, n) MAX = max(MAX, dp[n][i]) yield MAX+1 dp = [[-1]*len(G[i]) for i in range(N)] dfs(0, -1) def LRset(n): for i in range(1, len(G[n])): L[n][i] = max(L[n][i-1], dp[n][i-1]) for i in reversed(range(len(G[n])-1)): R[n][i] = max(R[n][i+1], dp[n][i+1]) L = [[0]*len(G[i]) for i in range(N)] R = [[0]*len(G[i]) for i in range(N)] LRset(0) @bootstrap def rerooting(n, pre, no): visited[n] = True preno = 0 for i in range(len(G[n])): if G[n][i] == pre: preno = i break dp[n][preno] = max(L[pre][no], R[pre][no])+1 LRset(n) for i in range(len(G[n])): if not visited[G[n][i]]: yield rerooting(G[n][i], n, i) yield visited = [False]*N visited[0] = True for i in range(len(G[0])): if not visited[G[0][i]]: rerooting(G[0][i], 0, i) ans = 0 for i in range(N): dp[i].sort(reverse=True) for j, d in enumerate(dp[i]): ans = max(ans, d*(j+1)+1) print(ans)