結果
問題 | No.806 木を道に |
ユーザー |
![]() |
提出日時 | 2019-07-10 20:22:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 650 bytes |
コンパイル時間 | 869 ms |
コンパイル使用メモリ | 81,980 KB |
実行使用メモリ | 154,268 KB |
最終ジャッジ日時 | 2024-11-06 05:54:20 |
合計ジャッジ時間 | 5,478 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
import syssys.setrecursionlimit(100000000)N = int(input())e = [ [] for i in range(N)]for i in range(N-1):a,b = map(int,input().split())a-=1b-=1e[a].append(b)e[b].append(a)#最も次数の小さい頂点から深さ優先探索。葉の枚数-1が答えcol = [ -1 for i in range(N)]ans = 0def dfs(n,c,pre):global ansif pre != -1 and len(e[n]) == 1 and e[n][0] == pre:ans += 1col[n] = cfor node in e[n]:if col[node] == -1:dfs(node,c+1,n)k = -1m = 10**10for i in range(N):if len(e[i]) < m:k = im = len(e[i])dfs(k,0,-1)print(ans-1)