白駿15900.ツリー脱出(with Python)

質問する

普段から仲の悪いメンバーと亨錫は、いよいよ真剣勝負.勝元と亨錫は2人とも親しい仁燮が対決を決めた.「木脱出」という将棋ゲームです.
「ツリー脱出」は、N個の頂点を持つツリー型ゲームボードと、いくつかのゲーム言語で構成されています.ツリーの各頂点には、番号1～Nが付いています.1番の頂点は「ルートノード」と呼ばれ、そのルートノードを中心に頂点間で親子関係が確立されます.サブノードがないことをリーフノードと呼びます.
このゲームは2人が交代でゲームボードの上でゲーム馬を移動するゲームです.最初は、木の中の各葉ノードにゲーム馬が置かれていました.誰かの番になると、現在存在するゲーム馬から1匹を選び、ノードの親ノードに移動します.この過程で、1つのノードに複数のゲーム馬が配置される可能性があります.このように移動すると、ゲーム馬がルートノードに到達すると、直ちにゲーム馬がクリアされる.すべてのプロセスが完了すると、次の人の番になります.このように続けていくと、ゲーム馬は存在せず、選べない人になります.
メンバーを軽んじる亨錫はあっさりとこのゲームのラインをメンバーに渡しただから成元はまず亨錫を始めてから始めますこれまでハンソクと対決するたびに負けてきたメンバーは、怒りに満ちていた.今度の対決で必ず勝って、ヘンソクの鼻を折ろうとした.だからゲームを始める前に、ゲームボードの形を見て、このゲームに勝つかどうかを事前に知りたいだけです.メンバーにこのゲームに勝てるかどうか教えてくれる番組を作ってメンバーを助けましょう

方法

問題を解決すること自体が簡単だ.
ルートノードから各リーフノードまでの深さを求めます.
全ての深さを加えて偶数と奇数でYes/Noと判断すればよい.

たとえば、左側
1番リーフノードまでの深さは2
リーフノード2番までの深さは1
2人合わせて3>>メンバー勝利
右側
1番リーフノードまでの深さは2
リーフノード2番までの深さは2
3番リーフノードまでの深さは1
3人合わせて5>>メンバー勝利
一方、

1番リーフノードまでの深さは2
リーフノード2番までの深さは2
3番リーフノードまでの深さは2
三つ合わせて6>>亨錫勝利
この方法で勝負が決まるといいです.
コードはまた、dfsで各リーフノードのdepthに保存され入力され、マージされ、偶、孔を識別する.
解決しましたが、データを入力するだけでタイムアウトになるかもしれません.
入力されたデータは最大50万個であるため,隣接行列を受信して確立するのに時間がかかる.
この問題を解決するために見つけたのはsysです.stdin.readline()を使用して入力をより迅速に受信します.
ただし、文字列のみを保存する場合は、最後尾の書き換え文字が同時に入力されるためです.rstrip()を追加する必要があります.

コード#コード#

import sys

N = int(input())

adj = [[] for _ in range(N+1)]
for i in range(N-1):
    n1, n2 = map(int, sys.stdin.readline().rstrip().split())
    adj[n1].append(n2)
    adj[n2].append(n1)

stack = [[1, 0]]
chk = [0] * (N+1)
chk[1] = -1


ls = []

while stack:
    cn, l = stack.pop()
    chk[cn] = 1

    if cn != 1 and len(adj[cn]) == 1:
        ls.append(l)
        continue

    for nn in adj[cn]:
        if chk[nn] == 0:
            stack.append([nn, l+1])