pythonで木の最小点披露を求めたい

実現したいこと

• 木の最小点披露を求めたい

前提

アルゴ式というサイトの木の最小点披露を求める問題についての質問です。解説で提示されているコードと自分で書いたコードの原理はほとんど変わらない気がするのですが上手くいきません。葉から探索をはじめ、親頂点が選ばれていなければ貪欲に選んでいくという手法を試しているのですがどこが間違っているのでしょうか？
アルゴ式-Q9. 木の最小点被覆

該当のソースコード

python

1from collections import deque 2 3# BFS ライクに頂点を見ていく関数4def bfs(children, par, ischosen):5 leaf = deque([]) # 探索すべき頂点を入れるキュー (最初は葉をいれる)6 # 自分の子頂点がすべて探索されたかチェックするための配列を作る7 deg = [0 for _ in range(N)] # deg[i]：頂点 i の子頂点数8 for v in range(N):9 deg[v] = len(children[v])10 if deg[v] == 0: leaf.append(v)11 12 while len(leaf):13 v = leaf.popleft()14 p = par[v]15 16 #親頂点が選ばれているなら選ばない17 if ischosen[p] or p == -1:18 continue19 20 if not ischosen[v]:21 ischosen[p] = True22 23 # 頂点 v の親頂点 p について、deg[p] を 1 減らす24 # p の子頂点たちがすべてチェックされた (deg[p] == 0) となったら、p もキューに入れる25 26 deg[p] -= 127 if deg[p] == 0:28 leaf.append(p)29 30 return31 32 33# main34# 入力の受け取り35N = int(input())36G = [[] for _ in range(N)] # グラフを表現する隣接リスト37for i in range(N-1):38 a, b = map(int, input().split())39 G[a].append(b)40 G[b].append(a)41 42# グラフを根付き木に変える43# 頂点 0 を根とする44r = 045# 根を始点として幅優先探索を行う46children = [[] for _ in range(N)] # children[i]：頂点 i の子頂点たちを格納する配列47par = [-1 for _ in range(N)] # par[i]：頂点 i の親頂点番号48seen = [False for _ in range(N)] # seen[i]：頂点 i を探索済みか49que = deque([]) # これから調べるべき頂点を管理するキュー50# 根を始点として登録する51seen[r] = True52par[r] = r 53que.append(r)54 55# キューが空になるまで、探索を続ける56while len(que) > 0:57 # 次に調べるべき頂点を v とする58 v = que.popleft()59 60 # 頂点 v に隣接する頂点 nv について、61 for nv in G[v]:62 # 頂点 nv が探索済みならば、スキップする63 if seen[nv]: continue64 # そうでないならば、children などの情報を更新してキューに nv を挿入する65 seen[nv] = True66 children[v].append(nv)67 par[nv] = v 68 que.append(nv)69 70ischosen = [False for _ in range(N)]71bfs(children, par, ischosen)72 73# 選ばれた頂点数が答え74ans = 075for v in range(N):76 if ischosen[v]: ans += 177print(ans)

正解のコード

python

1from collections import deque 2 3# BFS ライクに頂点を見ていく関数4def bfs(children, parent, ischosen):5 leaf = deque([]) # 探索すべき頂点を入れるキュー (最初は葉をいれる)6 # 自分の子頂点がすべて探索されたかチェックするための配列を作る7 deg = [0 for _ in range(N)] # deg[i]：頂点 i の子頂点数8 for v in range(N):9 deg[v] = len(children[v])10 if deg[v] == 0: leaf.append(v)11 12 while len(leaf):13 v = leaf.popleft()14 15 cnt = 0 # 子頂点のうち選ばれていない頂点数16 # v の子頂点 nv について、nv が選ばれているかを確認する17 for nv in children[v]:18 if not ischosen[nv]: cnt += 119 # cnt が 1 以上ならば、v を選ぶべき20 if cnt >= 1: ischosen[v] = True21 22 # 頂点 v の親頂点を p とする。頂点 v の親頂点が存在しない (v が根) ならば、これ以上何もしない23 p = parent[v]24 if p == -1: continue25 26 # 頂点 v の親頂点 p について、deg[p] を 1 減らす27 # p の子頂点たちがすべてチェックされた (deg[p] == 0) となったら、p もキューに入れる28 deg[p] -= 129 if deg[p] == 0:30 leaf.append(p)31 32 return33 34 35# main36# 入力の受け取り37N = int(input())38G = [[] for _ in range(N)] # グラフを表現する隣接リスト39for i in range(N-1):40 a, b = map(int, input().split())41 G[a].append(b)42 G[b].append(a)43 44# グラフを根付き木に変える45# 頂点 0 を根とする46r = 047# 根を始点として幅優先探索を行う48children = [[] for _ in range(N)] # children[i]：頂点 i の子頂点たちを格納する配列49parent = [-1 for _ in range(N)] # parent[i]：頂点 i の親頂点番号。存在しない場合は -150seen = [False for _ in range(N)] # seen[i]：頂点 i を探索済みか51que = deque([]) # これから調べるべき頂点を管理するキュー52# 根を始点として登録する53seen[r] = True54que.append(r)55 56# キューが空になるまで、探索を続ける57while len(que) > 0:58 # 次に調べるべき頂点を v とする59 v = que.popleft()60 61 # 頂点 v に隣接する頂点 nv について、62 for nv in G[v]:63 # 頂点 nv が探索済みならば、スキップする64 if seen[nv]: continue65 # そうでないならば、children などの情報を更新してキューに nv を挿入する66 seen[nv] = True67 children[v].append(nv)68 parent[nv] = v 69 que.append(nv)70 71ischosen = [False for _ in range(N)] # ischosen[i]：頂点 i は選ばれているか72# 葉のほうから探索を行う73bfs(children, parent, ischosen)74 75# 選ばれている頂点数が答え76ans = 077for v in range(N):78 if ischosen[v]: ans += 179print(ans)