結果

問題 No.763 Noelちゃんと木遊び
ユーザー None
提出日時 2021-04-14 03:39:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 274 ms / 2,000 ms
コード長 918 bytes
コンパイル時間 145 ms
コンパイル使用メモリ 82,072 KB
実行使用メモリ 110,744 KB
最終ジャッジ日時 2024-06-30 04:40:39
合計ジャッジ時間 5,896 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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

def dfs(start=0,goal=None):
parents={}
p,t=start,0
parents[p]=-2
next_set=[(~p,t),(p,t)]
if p==goal:
return t
while next_set:
p,t=next_set.pop()
if p>=0:
for q in edges[p]:
if q in parents:
continue
if q==goal:
return t+1
parents[q]=p
next_set.append((~q,t+1))
next_set.append((q,t+1))
else: #
p=~p
for q in edges[p]:
dp[0][p]+=max(dp[1][q],dp[0][q])
dp[1][p]+=dp[0][q]
dp[1][p]+=1
return -1
N=int(input())
edges=[[] for _ in range(N)]
for _ in range(N-1):
a,b=map(int, input().split())
a,b=a-1,b-1
edges[a].append(b)
edges[b].append(a)
dp=[[0]*N for _ in range(2)]
dfs(start=0,goal=None)
print(max(dp[0][0],dp[1][0]))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0