F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛备战资源(Noip提高组及以下),有意者请联系Lydsy2012@163.com,仅限教师及家长用户。
Problem 4730. -- Alice和Bob又在玩游戏

4730: Alice和Bob又在玩游戏

Time Limit: 40 Sec  Memory Limit: 512 MB
Submit: 374  Solved: 191
[Submit][Status][Discuss]

Description

Alice和Bob在玩游戏。有n个节点,m条边(0<=m<=n-1),构成若干棵有根树,每棵树的根节点是该连通块内编号最
小的点。Alice和Bob轮流操作,每回合选择一个没有被删除的节点x,将x及其所有祖先全部删除,不能操作的人输
。注:树的形态是在一开始就确定好的,删除节点不会影响剩余节点父亲和儿子的关系。比如:1-3-2 这样一条链
,1号点是根节点,删除1号点之后,3号点还是2号点的父节点。问有没有先手必胜策略。n<=10^5。

Input

Output

Sample Input

4
2 1
1 2
3 2
1 2
1 3
2 0
3 1
1 2

Sample Output

Alice
Alice
Bob
Alice

HINT

Source

[Submit][Status][Discuss]

HOME Back