Move Pieces

Alice and Bob are playing a game on a tree.

The tree has a total of $n$ nodes, connected by $n-1$ edges. At first, all the nodes are colored white, except node $1$ colored black, and a chess piece locates on node $1$ . Alice and Bob take turns to make moves, with Alice going first. On each turn, the player must select a white node and move the piece to that node. Simultaneously, all the nodes on the simple path between the original and the new position of the piece become black. Specify, The original and the new position become black. The player who cannot make any move immediately loses the game.

Both of the players want to know who will finally win the game, if they play optimally. As they have already started several games on different trees, you need to provide answers for $T$ independent test cases.

Alice 和 Bob 在玩游戏。

一开始有一棵 $n$ 个节点 $n-1$ 条边的树。一开始 $1$ 号节点是黑色的，剩下的节点是白色的。一个棋子放在 $1$ 号节点上。

Alice 或 Bob 每次需要选择一个白色的节点，并将棋子沿着树上的简单路径（最短路径）移动到这个节点，并染黑这个简单路径上的所有节点（包括起点和终点）。不能移动即没有白色节点可供选择的人输。

现在 Alice 和 Bob 轮流操作，他们都会采取最优策略，问谁能赢？Alice 先手。有 $T$ 组数据。

The first line contains a integer $T(1\le T\le 10^4)$ , the number of test cases.

For each test case, the first line contains a integer $n (1 \le n \le 2\times 10^5)$ , denoting the number of nodes.

Each of the next $n-1$ lines contains two integers. The $i$ -th line describes the $i$ -th edge containing two integers $u_i$ and $v_i$ , indicating the nodes connected by the $i$ -th edge.

It is guaranteed that the sum of all $n$ among a single test file is not greater than $2\times 10^5$ .

第一行一个正整数 $T(1\le T\le 10^4)$ ，表示数据组数。

对于每组数据，第一行一个整数 $n (1 \le n \le 2\times 10^5)$ 。

接下来 $n-1$ 行，每行两个整数 $u_i$ 和 $v_i$ ，描述一条树边。

题目保证，所有数据的 $n$ 的和不超过 $2\times 10^5$ .

For each testcase, output a line consisting of a single string $\texttt{Alice}$ or $\texttt{Bob}$ , representing the name of the winner.

对于每组数据，输出一行一个字符串表示答案。如果 Alice 能赢，输出 $\texttt{Alice}$ ，如果 Bob 能赢，输出 $\texttt{Bob}$ .

#include<bits/stdc++.h> using namespace std; const int N=200005; int n,T; vector<int>g[N]; inline int lob(int x){ return x&(-x); } pair<int,int> dfs(int u,int fa){ int x=0,y=0; for(int v:g[u]){ if(v==fa)continue; auto tmp=dfs(v,u); int i=tmp.first,j=tmp.second; x^=i; y|=j; } int z=lob((~x)&(~y)); x=(x/z+1)*z; y=(y/z+1)*z; return make_pair(x,y); } int main(){ cin>>T; while(T--){ cin>>n; for(int i=1;i<=n;i++){ g[i].clear(); } for(int i=1,u,v;i<n;i++){ cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } int ans=0; for(int u:g[1]){ ans^=dfs(u,1).first; } if(ans==0)cout<<"Bob"<<endl; else cout<<"Alice"<<endl; } return 0; }

详情