典型90【026 – Independent Set on a Tree（★4）】をpython解説

from collections import deque
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def bfs(Node,start,N):
    seen = [False]*N#初期情報
    seen[start] = True#スタート位置には到達済み
    dist = [1]*N#距離 ここでは、1が偶数回移動(blace) -1が奇数回移動(white)
    que = deque()
    que.append(start)

    while que:
        now = que.popleft()#取り出し
        for next in Node[now]:#取り出した頂点から行ける場所を探索
            if seen[next] == True:#すでに訪れたことがあれば探索しない
                continue
            elif seen[next] == False:#訪れたことがなかったら
                seen[next] = True#今訪れたのでFalseに変換
                dist[next] = dist[now]*-1#現在地と逆の色にする (-1をかけるとプラスマイナス入れ替わるから便利)
                que.append(next)#新しくqueリストに追加
    return dist


N = II()
[1 for i in range(N)]
edge = [[] for i in range(N)]
for i in range(N-1):
    A,B = MI()
    A-=1#0始まりにするため-1
    B-=1#0始まりにするため-1
    edge[A].append(B)#A頂点から移動できる頂点を追加
    edge[B].append(A)#B頂点から移動できる頂点を追加

dist = bfs(edge,0,N)


black = []#0番目の頂点から偶数回移動した頂点を集める
white = []#0番目の頂点から奇数回移動した頂点を集める
for i in range(N):
    if dist[i] == 1:
        black.append(i+1)#0始まりにしていたので、+1してもとに戻す
    else:
        white.append(i+1)#0始まりにしていたので、+1してもとに戻す
if len(black) >= N//2:#黒い頂点が、n//2以上あるなら
    print(*black[:N//2], sep=" ")
else:#黒い頂点が、n//2以下なら、白い頂点はn//2以上あるので
    print(*white[:N//2], sep=" ")