結果
問題 | No.1582 Vertexes vs Edges |
ユーザー |
![]() |
提出日時 | 2021-07-02 22:32:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 308 ms / 2,000 ms |
コード長 | 987 bytes |
コンパイル時間 | 180 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 109,028 KB |
最終ジャッジ日時 | 2024-06-29 12:21:13 |
合計ジャッジ時間 | 7,615 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
n=int(input()) graph=[] for i in range(n): graph.append([]) for i in range(n-1): a,b=map(int,input().split()) graph[a-1].append(b-1) graph[b-1].append(a-1) childcount=[0]*n children=[] for i in range(n): children.append([]) whitedp=[0]*n blackdp=[0]*n visited=[0]*n parent=[0]*n stack=[0] while stack: v=stack.pop() visited[v]=1 for i in graph[v]: if not visited[i]: stack.append(i) children[v].append(i) parent[i]=v stack=[] for i in range(n): childcount[i]=len(children[i]) if childcount[i]==0: stack.append(i) whitedp[i]=1 donechildcount=[0]*n while stack: v=stack.pop() par=parent[v] donechildcount[parent[v]]+=1 if donechildcount[parent[v]]==childcount[parent[v]]: stack.append(par) count=0 for chi in children[par]: count+=blackdp[chi] whitedp[par]=count+1 count=0 for chi in children[par]: count+=max(whitedp[chi],blackdp[chi]) blackdp[par]=count print(n-max(whitedp[0],blackdp[0]))