結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
![]() |
提出日時 | 2025-07-18 22:39:49 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,302 bytes |
コンパイル時間 | 390 ms |
コンパイル使用メモリ | 82,796 KB |
実行使用メモリ | 156,040 KB |
最終ジャッジ日時 | 2025-07-18 22:40:07 |
合計ジャッジ時間 | 15,877 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | WA * 30 |
ソースコード
# 全方位木DP # https://qiita.com/Kiri8128/items/a011c90d25911bdb3ed3#bottom-up-%E9%83%A8%E5%88%86 import sys input = sys.stdin.readline from collections import deque N=int(input()) X = [[] for i in range(N)] for i in range(N-1): x, y = map(int, input().split()) X[x-1].append(y-1) X[y-1].append(x-1) P = [-1] * N Q = deque([0]) R = [] while Q: i = deque.popleft(Q) R.append(i) for a in X[i]: if a != P[i]: P[a] = i X[a].remove(i) deque.append(Q, a) ##### Settings unit = [1] merge = lambda a, b: a + b adj_bu = lambda a, i: [max(a)+1] adj_td = lambda a, i, p: [max(a)+1] adj_fin = lambda a, i: min(a)*len(a) ##### ME = [unit] * N XX = [0] * N TD = [unit] * N for i in R[1:][::-1]: XX[i] = adj_bu(ME[i], i) p = P[i] ME[p] = merge(ME[p], XX[i]) XX[R[0]] = adj_fin(ME[R[0]], R[0]) # print("ME =", ME) # Merge before adj # print("XX =", XX) # Bottom-up after adj for i in R: ac = TD[i] for j in X[i]: TD[j] = ac ac = merge(ac, XX[j]) ac = unit for j in X[i][::-1]: TD[j] = adj_td(merge(TD[j], ac), j, i) ac = merge(ac, XX[j]) XX[j] = adj_fin(merge(ME[j], TD[j]), j) # print("TD =", TD) # Top-down after adj # print("XX =", XX) # Final Result print(max(XX))