結果

問題 No.763 Noelちゃんと木遊び
ユーザー 👑 rin204
提出日時 2022-03-23 20:48:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 287 ms / 2,000 ms
コード長 697 bytes
コンパイル時間 227 ms
コンパイル使用メモリ 81,900 KB
実行使用メモリ 97,312 KB
最終ジャッジ日時 2024-10-11 23:45:41
合計ジャッジ時間 6,300 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
edges[u].append(v)
edges[v].append(u)
stack = [0]
order = [0]
dist = [-1] * n
dist[0] = 0
while stack:
pos = stack.pop()
for npos in edges[pos]:
if dist[npos] != -1:
continue
dist[npos] = dist[pos] + 1
stack.append(npos)
order.append(npos)
dp1 = [0] * n
dp2 = [1] * n
for pos in order[::-1]:
for npos in edges[pos]:
if dist[npos] < dist[pos]:
continue
dp1[pos] += max(dp1[npos], dp2[npos])
dp2[pos] += max(dp1[npos], dp2[npos] - 1)
print(max(dp1[0], dp2[0]))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0