結果
問題 |
No.763 Noelちゃんと木遊び
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:29:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 265 ms / 2,000 ms |
コード長 | 1,696 bytes |
コンパイル時間 | 370 ms |
コンパイル使用メモリ | 82,652 KB |
実行使用メモリ | 121,796 KB |
最終ジャッジ日時 | 2025-03-22 10:44:30 |
合計ジャッジ時間 | 5,473 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
import sys from sys import stdin sys.setrecursionlimit(1 << 25) def main(): input = sys.stdin.read().split() n = int(input[0]) edges = [[] for _ in range(n+1)] ptr = 1 for _ in range(n-1): u = int(input[ptr]) v = int(input[ptr+1]) ptr += 2 edges[u].append(v) edges[v].append(u) # 木の構築と根の選択(根を1とする) # DPのためのグラフを構築する(親子関係を記録) parent = [0]*(n+1) children = [[] for _ in range(n+1)] stack = [1] visited = [False]*(n+1) visited[1] = True while stack: u = stack.pop() for v in edges[u]: if not visited[v]: visited[v] = True parent[v] = u children[u].append(v) stack.append(v) # DPを実行 selected = [0]*(n+1) not_selected = [0]*(n+1) stack = [] post_order = [] stack.append((1, False)) while stack: u, processed = stack.pop() if processed: post_order.append(u) continue stack.append((u, True)) for v in children[u]: stack.append((v, False)) for u in post_order: # selected[u] = 1 + sum not_selected of children s = 1 for v in children[u]: s += not_selected[v] selected[u] = s # not_selected[u] = sum max(selected[v], not_selected[v]) for children ns = 0 for v in children[u]: ns += max(selected[v], not_selected[v]) not_selected[u] = ns print(max(selected[1], not_selected[1])) if __name__ == "__main__": main()