結果

問題 No.2800 Game on Tree Inverse
ユーザー chineristACchineristAC
提出日時 2024-06-28 21:28:46
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,926 bytes
コンパイル時間 139 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 528,872 KB
最終ジャッジ日時 2024-06-28 21:30:49
合計ジャッジ時間 110,715 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 56 MLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
出力含めてまったく同じ問題作問しててびっくり！
"""

class BinaryTrie:
    class node:
        def __init__(self):
            self.left = None
            self.right = None
            self.cnt = 0

    def __init__(self,n):
        self.root = self.node()
        self.n = n
        self.xor = 0
        self.set = set()
    
    def __len__(self):
        return self.root.cnt
    
    def __str__(self):
        res = []
        for val in self.set:
            res.append(val^self.xor)
        res.sort()
        res = ["["] + [str(val)+", " for val in res] + ["]"]
        return "".join(res)
    
    def append(self,x):
        x ^= self.xor
        if x in self.set:
            return 
        self.set.add(x)

        pos = self.root
        for i in range(self.n-1,-1,-1):
            pos.cnt += 1
            if x>>i & 1:
                if pos.right is None:
                    pos.right = self.node()
                pos = pos.right
            else:
                if pos.left is None:
                    pos.left = self.node()
                pos = pos.left
        pos.cnt = 1
    
    def all_prod(self,x):
        self.xor ^= x
    
    def mex(self):
        res = 0
        pos = self.root
        t = 1<<self.n
        for i in range(self.n-1,-1,-1):
            t >>= 1
            if self.xor>>i & 1:
                check = 0
                if pos.right:
                    check = pos.right.cnt
                if check==t:
                    res += t
                    if not pos.left:
                        return res
                    else:
                        pos = pos.left
                else:
                    if not pos.right:
                        return res
                    else:
                        pos = pos.right
            else:
                check = 0
                if pos.left:
                    check = pos.left.cnt
                if check==t:
                    res += t
                    if not pos.right:
                        return res
                    else:
                        pos = pos.right
                else:
                    if not pos.left:
                        return res
                    else:
                        pos = pos.left
        
        return res

import sys,random
from collections import deque

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

def solve(N,edge):
    parent = [-1] * N
    
    deq = deque([0])
    topo = []
    while deq:
        v = deq.popleft()
        topo.append(v)
        for nv in edge[v]:
            if nv == parent[v]:
                continue
            parent[nv] = v
            deq.append(nv)
    
    
    grundy = [-1 for v in range(N)]
    BT = [BinaryTrie(17) for i in range(N)]

    def merge(v,pv):
        if len(BT[v]) > len(BT[pv]):
            BT[v],BT[pv] = BT[pv],BT[v]

        x = BT[v].xor
        for val in BT[v].set:
            BT[pv].append(x^val)
    
    for v in topo[::-1]:
        BT[v].append(0)
        G = 0
        for nv in edge[v]:
            if nv == parent[v]:
                continue
            G ^= grundy[nv]
            BT[nv].all_prod(grundy[nv])
            merge(nv,v)

        BT[v].all_prod(G)
        grundy[v] = BT[v].mex()
    
    CG = [0 for v in range(N)]
    for v in range(N):
        for nv in edge[v]:
            if parent[v]==nv:
                continue
            CG[v] ^= grundy[nv]
    
    
    res = []
    tmp = [0 for v in range(N)]
    for v in topo:
        if CG[v]^tmp[v]==0:
            res.append(v+1)
        for nv in edge[v]:
            tmp[nv] = tmp[v]^CG[v]^grundy[nv]

    return sorted(res)

N = int(input())
edge = [[] for v in range(N)]
for i in range(N-1):
    u,v = mi()
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

res = solve(N,edge)
print("Alice")
print(len(res))
print(*res)
0