这题感觉好神仙，还是没有自己独立想出来。
题目分析
如果 \(u,v\) 是祖先关系，那么我们就给 \(u,v\) 连上一条双向边，现在问题就变成了：给定一张无向图， Alice 选择从某处开始放一个棋子，然后 Bob 和 Alice 依次移动这个棋子，但是不能走到到过的地方，无法操作者败。
结论就是：如果有完美匹配，那么 Bob 胜，否则 Alice 胜。
结论证明：
一、有完美匹配。
此时 Bob 只需要根据 Alice 走到的位置，然后走它在完美匹配中匹配到的点即可，这样最终 Alice 会无路可走。
二、没有完美匹配。
不妨设最大匹配为 \((a_1,a_2),(a_3,a_4),\dots\) ，那么假如 Alice 从一个没有在最大匹配中的点开始，那么 Bob 显然不可能再走到一个没有在最大匹配中的点，否则就形成了一条增广路，所以 Alice 就用“有完美匹配”中 Bob 的策略即可胜利。
由于是题目给的是一棵树，所以很好求最大匹配，设 \(dp_u\) 表示 \(u\) 这棵子树中最少有多少点没有匹配到即可。
参考代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int maxn=100005;
struct Edge{
int v,nt;
Edge(int v=0,int nt=0):
v(v),nt(nt){}
}e[maxn*2];
int hd[maxn],num;
void qwq(int u,int v){
e[++num]=Edge(v,hd[u]),hd[u]=num;
}
int dp[maxn];
void dfs(int u,int fa){
dp[u]=-1;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);dp[u]+=dp[v];
}
dp[u]=(dp[u]<0?-dp[u]:dp[u]);
}
int main(){
int n;read(n);
for(int i=1;i<n;++i){
int u,v;
read(u),read(v);
qwq(u,v);qwq(v,u);
}
dfs(1,0);
puts(dp[1]?"Alice":"Bob");
return 0;
}