結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
|
提出日時 | 2022-06-12 19:43:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 292 ms / 2,000 ms |
コード長 | 606 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 81,716 KB |
実行使用メモリ | 105,020 KB |
最終ジャッジ日時 | 2024-09-23 06:14:35 |
合計ジャッジ時間 | 6,576 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
N = int(input())G = [[] for _ in range(N)]for _ in range(N - 1):u,v = map(int,input().split())u -= 1v -= 1G[u].append(v)G[v].append(u)stack = [(0,-1),(~0,-1)]dp = [[0,1] for _ in range(N)]while stack:now,parent = stack.pop()if now < 0:now = ~nowfor v in G[now]:if v == parent:continuestack.append((v,now))stack.append((~v,now))continuefor v in G[now]:if v == parent:continuedp[now][0] += max(dp[v])dp[now][1] += max(dp[v][0],dp[v][1] - 1)print(max(dp[0]))#print(dp)