Problem:


Score : 1100 points

Problem Statement

There is a tree with N vertices numbered 1, 2, ..., N.
The edges of the tree are denoted by (x_i, y_i).

On this tree, Alice and Bob play a game against each other.
Starting from Alice, they alternately perform the following operation:

Select an existing edge and remove it from the tree, disconnecting it into two separate connected components. Then, remove the component that does not contain Vertex 1.

A player loses the game when he/she is unable to perform the operation.
Determine the winner of the game assuming that both players play optimally.

Constraints

2 \leq N \leq 100000

1 \leq x_i, y_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_{N-1} y_{N-1}

Output

Print Alice if Alice wins; print Bob if Bob wins.

Sample Input 1

5
1 2
2 3
2 4
4 5

Sample Output 1

Alice

If Alice first removes the edge connecting Vertices 1 and 2, the tree becomes a single vertex tree containing only Vertex 1.
Since there is no edge anymore, Bob cannot perform the operation and Alice wins.

Sample Input 2

5
1 2
2 3
1 4
4 5

Sample Output 2

Bob

Sample Input 3

6
1 2
2 4
5 1
6 3
3 2

Sample Output 3

Alice

Sample Input 4

7
1 2
3 7
4 6
2 3
2 4
1 5

Sample Output 4

Bob



Sample input:
5
1 2
2 3
2 4
4 5


Sample output:
Alice

Submission status: Wrong Answer

Solution code:
n = int(input())
cnt = 0
xy = [list(map(int, input().split())) for i in range(n - 1)]
for x,y in xy:
	if x == 1:
		cnt += 1
print(["Bob", "Alice"][cnt % 2])

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)

N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)

def grundy(v,pv):
    if v==0:
        if len(edge[v])==1:
            return grundy(edge[0][0],0)+1
        else:
            res=0
            for nv in edge[v]:
                if nv!=pv:
                    res^=grundy(nv,v)
            return res
    else:
        if len(edge[v])==1:
            return 0
        elif len(edge[v])==2:
            for nv in edge[v]:
                if nv!=pv:
                    return grundy(nv,v)+1
        else:
            res=0
            for nv in edge[v]:
                if nv!=pv:
                    res^=grundy(nv,v)
            return res


ans=grundy(0,-1)
if ans!=0:
    print("Alice")
else:
    print("Bob")

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    N, A, B, C, D = LI()
    for i in range(N-1):
        low = A + i*C - (N-1-i)*D
        up = A + i*D - (N-1-i)*C
        if low<=B<=up:
            print("YES")
            return
    print("NO")
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        x, y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        V[y].append(x)
    def dfs(s,p):
        grundy = 0
        judge = len(V[s])
        if p==-1:
            judge += 1
        if judge==1:
            return grundy
        if judge==2:
            for v in V[s]:
                if v == p:
                    continue
                cur = dfs(v, s)
                grundy = cur+1
            return grundy
        for v in V[s]:
            if v==p:
                continue
            cur = dfs(v,s)
            grundy ^= cur

        return grundy
    ans = "Alice"
    if dfs(0,-1)==0:
        ans = "Bob"
    print(ans)
    return

def examE():
    N, H = LI()
    A = [LI()for _ in range(N)]


    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)


if __name__ == '__main__':
    examD()

"""

"""

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.readline
sys.setrecursionlimit(1000000)

N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)

def dfs(v,pv):
    if v==0:
        if len(edge[v])%2==1:
            return True
        else:
            ans=0
            for nv in edge[v]:
                ans+=int(dfs(nv,v))
            return ans%2==1
    else:
        if len(edge[v])%2==0:
            return True
        else:
            ans=0
            for nv in edge[v]:
                if nv!=pv:
                    ans+=int(dfs(nv,v))
                else:
                    continue
            return ans%2==1

answer=dfs(0,-1)
if answer:
    print("Alice")
else:
    print("Bob")

Submission status: Wrong Answer

Solution code:
print("Alice")

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)

def dfs(v,pv):
    if v==0:
        if len(edge[v])%2==1:
            return True
        else:
            ans=0
            for nv in edge[v]:
                ans+=int(dfs(nv,v))
            return ans%2==1
    else:
        if len(edge[v])%2==0:
            return True
        else:
            ans=0
            for nv in edge[v]:
                if nv!=pv:
                    ans+=int(dfs(nv,v))
            return ans%2==1

answer=dfs(0,-1)
if answer:
    print("Alice")
else:
    print("Bob")

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)

def dfs(v,pv):
    if v==0:
        if len(edge[v])%2==1:
            return True
        else:
            ans=0
            for nv in edge[v]:
                ans+=int(dfs(nv,v))
            return ans%2==1
    else:
        if len(edge[v])%2==0:
            return True
        else:
            ans=0
            for nv in edge[v]:
                if nv!=pv:
                    ans+=int(dfs(nv,v))
            return ans%2==1

ans=dfs(0,-1)
if ans:
    print("Alice")
else:
    print("Bob")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = [0]
    q2 = []
    g = [0]*n
    bfs = [1]*n
    bfs[0] = 0
    d = [0]*n
    while q:
        x = q.pop()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                d[x] += 1
                q.append(y)
                q2.append((x,y))
    while q2:
        x,y = q2.pop()
        if d[x] > 1:
            g[x] ^= g[y]
        else:
            g[x] = g[y]+1
    ans = g[0]
    if ans:
        print("Alice")
    else:
        print("Bob")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


def solve(v, parent=None):
    # v を葉にした状態で相手に渡せるなら 2、渡せないなら 1 とすると
    # 子の 2 を 1 に変えるか取り除くか選べるので Nim になる
    xor = 0
    for u in graph[v]:
        if parent == u:
            continue
        xor ^= solve(u, parent=v)
    return 2 if xor > 0 else 1


ans = solve(0)
if ans == 2:
    print('Alice')
else:
    print('Bob')

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
XY = (tuple(int(x)-1 for x in line.split()) for line in readlines())

graph = [[] for _ in range(N)]
for x,y in XY:
    graph[x].append(y)
    graph[y].append(x)

visited = [True] + [False] * (N-1)
q = [1]
ord = [1]
par = [0] * N
while q:
    x = q.pop()
    for y in graph[x]:
        if visited[y]:
            continue
        ord.append(y)
        par[y] = x
        visited[y] = True
        q.append(y)

G = [0] * (N+1)
for x in ord[:0:-1]:
    p = par[x]
    G[p] ^= (G[x]+1)

answer = 'Alice' if G[0] != 0 else 'Bob'
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	adj[y-1].append(x-1)

nim = []

for i in adj[0]:
	dist = [10**10 for _ in range(n)]
	c = Counter()
	dist[0] = 0
	dist[i] = 1
	c[1] += 1
	s = [i]
	d_max = 1
	while s:
		l = s.pop()
		for v in adj[l]:
			if dist[v] == 10**10:
				dist[v] = dist[l]+1
				c[dist[v]] += 1
				d_max = max(d_max, dist[v])
				s.append(v)
	tmp = 0
	for j in range(d_max, 0, -1):
		tmp += 1
		if c[j]%2 == 0:
			tmp ^= 1
	nim.append(tmp)

res = 0
for z in nim:
	res ^= z

if res == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	adj[y-1].append(x-1)

nim = []

for i in adj[0]:
	dist = [10**10 for _ in range(n)]
	c = Counter()
	dist[0] = 0
	dist[i] = 1
	s = [i]
	d_max = 1
	while s:
		l = s.pop()
		for v in adj[l]:
			if dist[v] == 10**10:
				dist[v] = dist[l]+1
				c[dist[v]] += 1
				d_max = max(d_max, dist[v])
				s.append(v)
	tmp = 1
	for j in range(d_max, 0, -1):
		if c[j]%2 == 0:
			tmp ^= 1
		else:
			tmp += 1
	nim.append(tmp)

res = 0
for z in nim:
	res ^= z

if res == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	adj[y-1].append(x-1)

nim = []

for i in adj[0]:
	dist = [10**10 for _ in range(n)]
	c = Counter()
	dist[0] = 0
	dist[i] = 1
	s = [i]
	d_max = 1
	while s:
		l = s.pop()
		for v in adj[l]:
			if dist[v] == 10**10:
				dist[v] = dist[l]+1
				c[dist[v]] += 1
				d_max = max(d_max, dist[v])
				s.append(v)
	tmp = d_max
	sgn = -1
	for j in range(d_max, 1, -1):
		if c[j]%2 == 0:
			tmp += sgn
		else:
			sgn *= -1
	nim.append(tmp)

res = 0
for z in nim:
	res ^= z

if res == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	adj[y-1].append(x-1)

nim = []

for i in adj[0]:
	dist = [10**10 for _ in range(n)]
	c = Counter()
	dist[0] = 0
	dist[i] = 1
	s = [i]
	d_max = 1
	while s:
		l = s.pop()
		for v in adj[l]:
			if dist[v] == 10**10:
				dist[v] = dist[l]+1
				c[dist[v]] += 1
				d_max = max(d_max, dist[v])
				s.append(v)
	tmp = d_max
	for j in range(d_max, 1, -1):
		if c[j]%2 == 0:
			if (d_max-j)%2 == 0:
				tmp -= 1
			else:
				tmp += 1
			d_max = j-1
	nim.append(tmp)

res = 0
for z in nim:
	res ^= z

if res == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Wrong Answer

Solution code:
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello

print "Alice"

Submission status: Wrong Answer

Solution code:
#Game on Tree
N = int(input())
a = []
for i in range(N-1):
    a.append( list(map(int, input().split())) ) 

b = []
for s in a:
    b.extend(s)
t = b.count(1)
if t:
    print("Alice")
else:
    print("Bob")

Submission status: Wrong Answer

Solution code:
n = int(input())
c = 0
for i in range(n-1):
    a,b = list(map(int,input().split()))
    if a == 1:
        c += 1

if c%2 == 1:
    print("Alice")
else:
    print("Bob")

Submission status: Wrong Answer

Solution code:
n = int(input())
x=[0]*n
y = [0]*n
flag = 0
for i in range(n-1):
    x[i], y[i] = list(map(int,input().split(" ")))
    if x[i] == 1:
        flag+=1
    if y[i] == 1:
        flag+=1

if flag==2:
    if n%2==0:
        print("Alice")
    else:
        print("Bob")
else:
    print("Alice")

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    e = collections.defaultdict(set)
    for _ in range(n-1):
        x,y = LI()
        e[x].add(y)
        e[y].add(x)

    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv in e[u]:
                ud = 1
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    d = search(1)
    dd = collections.defaultdict(int)
    for i in range(2,n+1):
        dd[d[i]] += 1
    if dd[1] == 1:
        return 'Alice'
    k = 0
    for i,c in dd.items():
        if c % 2 == 1:
            return 'Alice'
    if k % 2 == 1:
        return 'Alice'
    return 'Bob'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    e = collections.defaultdict(set)
    for _ in range(n-1):
        x,y = LI()
        e[x].add(y)
        e[y].add(x)

    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv in e[u]:
                ud = 1
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    d = search(1)
    dd = collections.defaultdict(int)
    for i in range(2,n+1):
        dd[d[i]] += 1
    if dd[1] == 1:
        return 'Alice'
    k = 0
    for i,c in dd.items():
        if c % 2 == 1:
            k += 1
    if k % 2 == 1:
        return 'Alice'
    return 'Bob'


print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(lambda x: int(x) - 1, input().split())
    G[x].append(y)
    G[y].append(x)

nim = [0] * N

def dfs(v, p):
    for c in G[v]:
        if c != p:
            dfs(c, v)
            nim[v] ^= nim[c]
    nim[v] += 1

dfs(0, -1)
print('Alice' if nim[0] > 1 else 'Bob')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N=int(input())
g = [[] for i in range(N)]
for i in range(N-1):
	a,b=map(int,input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)

nim = [-1 for i in range(N)]

def dfs(cur,par):
	val = 0
	for dst in g[cur]:
		if dst == par:
			continue
		val ^= dfs(dst,cur) + 1
	nim[cur] = val
	return val

dfs(0 , -1)
#print(nim)
if nim[0] == 0:
	print('Bob')
else:
	print('Alice')

Submission status: Time Limit Exceeded

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def DFS(G, XOR, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, XOR, visit, i)
			XOR[node] ^= XOR[i] + 1

#処理内容
def main():
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		x, y = getlist()
		x -= 1
		y -= 1
		G.add_edge(x, y)
		G.add_edge(y, x)

	#計算
	XOR = [0] * N
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, XOR, visit, 0)
	if XOR[0] == 0:
		print("Bob")
	else:
		print("Alice")
	

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def DFS(G, XOR, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, XOR, visit, i)
			XOR[node] = XOR[node] ^ (XOR[i] + 1)

#処理内容
def main():
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		x, y = getlist()
		x -= 1
		y -= 1
		G.add_edge(x, y)
		G.add_edge(y, x)

	#計算
	XOR = [0] * N
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, XOR, visit, 0)
	if XOR[0] == 0:
		print("Bob")
	else:
		print("Alice")
	

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, decrement=1):
        self.n = n
        self.edges = [[] for _ in range(n)]
        self.root = None
        self.depth = [-1]*n
        self.size = [1]*n       # 部分木のノードの数
        self.decrement = decrement

    def add_edge(self, u, v):
        u, v = u-self.decrement, v-self.decrement
        self.edges[u].append(v)
        self.edges[v].append(u)

    def add_edges(self, edges):
        for u, v in edges:
            u, v = u-self.decrement, v-self.decrement
            self.edges[u].append(v)
            self.edges[v].append(u)

    def set_root(self, root):
        root -= self.decrement
        self.root = root
        self.par = [-1]*self.n
        self.depth[root] = 0
        self.order = [root]     # 帰りがけに使う
        next_set = [root]
        while next_set:
            p = next_set.pop()
            for q in self.edges[p]:
                if self.depth[q] != -1: continue
                self.par[q] = p
                self.depth[q] = self.depth[p]+1
                self.order.append(q)
                next_set.append(q)
        for p in self.order[::-1]:
            for q in self.edges[p]:
                if self.par[p] == q: continue
                self.size[p] += self.size[q]


#########################################################################################################
import sys
input = sys.stdin.readline

N = int(input())
T = Tree(N, decrement=1)
for _ in range(N-1):
    x, y = map(int, input().split())
    T.add_edge(x, y)
T.set_root(1)

grundy = [0]*N
for p in T.order[::-1]:
    for q in T.edges[p]:
        if T.par[p]==q: continue
        grundy[p]^=grundy[q]+1

print("Alice" if grundy[0]!=0 else "Bob")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
    x, y = map(int, input().split())
    edges[x - 1].append(y - 1)
    edges[y - 1].append(x - 1)
def grundy_dfs(cur, prev):
    res = 0
    for next_ in edges[cur]:
        if next_ == prev:
            continue
        res ^= grundy_dfs(next_, cur) + 1
    return res
if grundy_dfs(0, -1) > 0:
    print("Alice")
else:
    print("Bob")

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.order = []
        self.order.append(root)
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.order.append(adj)
                    stack.append(adj)

N = int(input())
edge = [tuple(map(int, input().split())) for _ in range(N - 1)]

tree = Tree(N, edge)
tree.setroot(0)

grundy = [0 for _ in range(N)]

for node in tree.order[::-1]:
    for adj in tree.tree[node]:
        if tree.parent[node] == adj:
            continue
        grundy[node] ^= grundy[adj] + 1

print('Alice' if grundy[0] != 0 else 'Bob')

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N = int(input())
adj = [[] for _ in range(N)]
for i in range(N - 1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    adj[x].append(y)
    adj[y].append(x)


def dfs(v, p):
    nim = 0
    for u in adj[v]:
        if u == p:
            continue
        nim ^= dfs(u, v)
    if p == -1:
        return nim
    nim += 1
    return nim

res = dfs(0, -1)

if res:
    print("Alice")
else:
    print("Bob")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10,6))

N = int(input())
Edges = list([] for _ in range(N))
for n in range (N-1):
    x, y = map(int, input().split())
    Edges[x-1].append(y-1)
    Edges[y-1].append(x-1)

def dfs(cur_node, parent_node):
    grundy = 0
    for child_node in Edges[cur_node]:
        if child_node != parent_node:
            grundy ^= (dfs(child_node, cur_node) + 1)
    return grundy

G = dfs(0, -1)
if G == 0:
    print("Bob")
else:
    print("Alice")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10,6))

N = int(input())
Edges = list([] for _ in range(N))
for n in range (N-1):
    x, y = map(int, input().split())
    Edges[x-1].append(y-1)
    Edges[y-1].append(x-1)

def dfs(cur_node, parent_node):
    grundy = 0
    for child_node in Edges[cur_node]:
        if child_node == parent_node:
            continue
        else:
            grundy ^= (dfs(child_node, cur_node) + 1)
    return grundy

G = dfs(0, -1)
if G == 0:
    print("Bob")
else:
    print("Alice")

Submission status: Accepted

Solution code:
def topological_sort(tree: list, root) -> list:
    """根付き木をトポロジカルソートする"""
    n = len(tree)
    visited = [False] * n
    visited[root] = True
    tp_sorted = [root]
    stack = [root]
    while stack:
        v = stack.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v]:
                continue
            visited[nxt_v] = True
            stack.append(nxt_v)
            tp_sorted.append(nxt_v)
    return tp_sorted


def get_par(tree: list, root: int) -> list:
    """根付き木の頂点それぞれの親を求める"""
    n = len(tree)
    visited = [False] * n
    visited[root] = True
    par = [-1] * n
    stack = [root]
    while stack:
        v = stack.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v]:
                continue
            visited[nxt_v] = True
            stack.append(nxt_v)
            par[nxt_v] = v
    return par


n = int(input())
edges = [list(map(int, input().split())) for i in range(n - 1)]


tree = [[] for i in range(n)]
root = 0
for a, b in edges:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

tp_sorted = topological_sort(tree, root)
par = get_par(tree, root)
grandy = [0] * n

for v in tp_sorted[::-1]:
    par_v = par[v]
    if par_v == -1:
        continue
    grandy[par_v] ^= grandy[v] + 1

if grandy[0] != 0:
    print("Alice")
else:
    print("Bob")

Submission status: Accepted

Solution code:
import sys
n=int(input())
sys.setrecursionlimit(k:=2*n)
T=[[]for _ in"_"*k]
for _ in range(n-1):a,b=map(int,input().split());T[a]+=b,;T[b]+=a,
def d(v,p):
 r=0
 for s in T[v]:
  if s!=p:r^=d(s,v)+1
 return r
print("ABloibc e"[d(1,1)<1::2])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(9**9)
n=int(input())
T=[[]for _ in"_"*(n+1)]
for _ in range(n-1):a,b=map(int,input().split());T[a]+=b,;T[b]+=a,
def d(v,p):
 r=0
 for s in T[v]:
  if s!=p:r^=d(s,v)+1
 return r
print("ABloibc e"[d(1,1)<1::2])

Submission status: Accepted

Solution code:
def examA():
    N = I()
    A = LI()
    D = defaultdict(int)
    for a in A:
        D[a] += 1
    ans = 0
    for key,d in D.items():
        if key>d:
            ans += d
        else:
            ans += d - key
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+A[i]
    D = defaultdict(int)
    for s in S:
        D[s] += 1
    ans = 0
    for d in D.values():
        ans += d*(d-1)//2
    print(ans)
    return

def examC():
    N, A, B, C = LI()
    L = [I()for _ in range(N)]
    loop = (1<<(2*N))
    ans = inf
    for l in range(loop):
        cost = 0
        bamboo_A = 0
        bamboo_B = 0
        bamboo_C = 0
        for j in range(N):
            if l&(1<<(2*j))>0:
                if l&(1<<(2*j+1))>0:
                    cost += 10
                    bamboo_A += L[j]
                else:
                    cost += 10
                    bamboo_B += L[j]
            else:
                if l&(1<<(2*j+1))>0:
                    cost += 10
                    bamboo_C += L[j]
        if bamboo_A==0 or bamboo_B==0 or bamboo_C==0:
            continue
        cost += abs(A-bamboo_A) + abs(B-bamboo_B) + abs(C-bamboo_C) - 30
        ans = min(ans,cost)

    print(ans)
    return

def examD():
    N = I()
    P = LI()
    O_ = [-1]*N
    start = P[0]-1
    for i in range(N):
        O_[P[i]-1] = i
    #print(O_,start)
    A = [1]*N
    B = [1]*N
    for i in range(start+1,N):
        cur = O_[i]-O_[i-1]
        if cur>0:
            A[i] = A[i-1] + (cur+1)
            B[i] = B[i-1] - 1
        else:
            A[i] = A[i-1] + 1
            B[i] = B[i-1] - (-cur+1)
    for i in range(start)[::-1]:
        cur = O_[i]-O_[i+1]
        if cur>0:
            B[i] = B[i+1] + (cur+1)
            A[i] = A[i+1] - 1
        else:
            B[i] = B[i+1] + 1
            A[i] = A[i+1] - (-cur+1)
    if A[0]<1:
        add = (1-A[0])
        for i in range(N):
            A[i] += add
    if B[-1]<1:
        add = (1-B[-1])
        for i in range(N):
            B[i] += add

    print(" ".join(map(str,A)))
    print(" ".join(map(str,B)))
    return

def examE():
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        x, y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        V[y].append(x)
    def dfs(s,p=-1):
        loop = 0
        grundy = 0
        children = []
        for v in V[s]:
            if v==p:
                continue
            loop += 1
            children.append(dfs(v,s)+1)
        if loop==1:
            grundy = children[0]
        elif loop>1:
            for c in children:
                grundy ^= c
        return grundy
    if dfs(0):
        print("Alice")
    else:
        print("Bob")
    return

def examF():
    ans = 0
    print(ans)
    return


from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
9
7 3 9 1 8 4 5 6 2
"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
def dfs(v, par=-1):
  res = 0
  for nv in T[v]:
    if nv == par:
      continue
    res ^= dfs(nv, v)+1
  return res
if dfs(0) == 0:
  print("Bob")
else:
  print("Alice")