HDU6741 题解
$\text{Description}$
$T$ 次询问，每次询问给定一个 $n$ 点有根树，树根为 $1$。两人博弈，每次可以选正整数个叶节点删除，无法操作者失败，问先手必胜还是后手必胜。
$\sum n\le 10^6$
$\text{Solution}$
考虑已有一棵树 $T$，选择其一个非叶节点，然后给这个非叶节点挂上一个节点当儿子，得到新树 $T’$。分类讨论：
- $T$ 先手必胜，则将第一步策略加上新加入的节点（挂在非叶节点上，所以不影响第一步策略），此时 $T’$ 先手必胜。
- $T$ 后手必胜，则对于 $T’$，第一步删去新加入的节点，此时 $T’$ 先手必胜。
换句话说，对于一棵树，若一个儿子数大于 $1$ 的节点有一个儿子是叶节点，那么这棵树是先手必胜的。
同时可以证明除了一条链之外所有先手必胜的树都可以通过操作得到一个满足上面条件的树。
然后我们考虑怎么让一棵树变成满足条件的树。我们可以把叶子节点到根路径上满足点度大于 $1$ 且深度最大的点与该叶子节点的路径上包含的点数写出来，可以得到一个序列。
可以发现，每次操作等价于选序列中的若干个数减一，而此时胜利条件变味了当前序列中有一个数为 $1$（此时一条链的情况也与此相同了，只需令满足条件的点为根即可）。
容易发现最极限的必胜态是有一个数为 $1$，最极限的必败态是所有数都为 $2$，我们猜想一个局面为必败态当且仅当序列中所有数都为偶数，一个局面为必胜态当且仅当存在一个数为奇数。
然后容易发现，当存在奇数时，我们总能将所有奇数变为偶数；当所有数都为偶数时，我们不得不让局面出现奇数。这样就证明了上面的猜想。
$\text{Code}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
#define REG register
#define MAXN 1000005
using namespace std;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
int T,n;
struct Edge{int v,nxt;}ed[MAXN<<1];
int head[MAXN],cnt;
inline void adde(int u,int v){ed[++cnt]=(Edge){v,head[u]},head[u]=cnt;}
inline void add(int u,int v){adde(u,v),adde(v,u);}
#define FORE(i,Now) for(REG int i=head[Now];i;i=ed[i].nxt)
int deg[MAXN],top[MAXN];
void dfs(int Now,int Fa){
if(deg[Fa]>1) top[Now]=1;
else top[Now]=Fa?top[Fa]+1:1;
FORE(i,Now)
if(ed[i].v^Fa) dfs(ed[i].v,Now);
}
inline void Solve(){
read(n),cnt=0;
memset(deg,0,sizeof deg),memset(head,0,sizeof head);
for(REG int i=2;i<=n;++i){int fa;read(fa),add(i,fa),++deg[fa];}
dfs(1,0);
for(REG int i=1;i<=n;++i)
if((!deg[i])&&(top[i]&1)){puts("Takeru");return;}
puts("Meiya");
}
int main(){
read(T);
while(T--) Solve();
}
|
