結果

問題 No.3719 Share the Tree
コンテスト
ユーザー 👑 loop0919
提出日時 2026-08-26 21:02:14
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 255 ms / 2,000 ms
+ 3µs
コード長 937 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 82 ms
コンパイル使用メモリ 81,024 KB
実行使用メモリ 84,480 KB
平均クエリ数 2.00
最終ジャッジ日時 2026-09-18 20:50:41
合計ジャッジ時間 7,115 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

player = input()

# フェーズ 1
N = int(input())
k = N - 2
print(k)

# フェーズ 2
if player == "Alice":
    # Alice の操作
    tree = [set() for _ in range(N)]

    for _ in range(N - 1):
        u, v = [int(s) - 1 for s in input().split()]
        tree[u].add(v)
        tree[v].add(u)

    leaves = {i for i in range(N) if len(tree[i]) == 1}
    A = []

    for _ in range(k):
        v = min(leaves)
        leaves.discard(v)

        a = tree[v].pop()
        tree[a].discard(v)

        if len(tree[a]) == 1:
            leaves.add(a)

        A.append(a + 1)

    print(*A)

else:
    # Bob の操作
    A = [int(s) - 1 for s in input().split()]
    B = []

    edges = []

    for i, a in enumerate(A):
        b = min(set(range(N)) - set(A[i:] + B))

        B.append(b)
        edges.append((a, b))

    b = min(set(range(N)) - set(B))
    edges.append((b, N - 1))

    for u, v in edges:
        print(u + 1, v + 1)
0