P8347 题解

· · 题解

前言

题目传送门！

更好的阅读体验？

困难的博弈论题目。参考了巨佬 @Kaenbyou_Rin 的题解，并对他题解中错误的地方进行了更改。

警告：以下内容稍长，请认真阅读，有一定数学基础就很容易理解，因为实际证明难度不高。这个是感性证明。

思路

首先给出结论：只要有一个节点的度是偶数，先手必胜；否则后手必胜（也就是：后手必胜当且仅当全部节点的度都是奇数）。

证明如下。为了方便叙述，设状态 A 表示全部点度都是奇数。设每一步选择删除的点为 u。严谨说明，这里都是看 n > 1 的情况。

首先很显然，状态 A 的下一个状态一定不是 A。

因为 u 连接的点都是两两不同的，所以删掉对应的边后，u 所连接的点的度一定都会变成偶数。

这样不管选哪个连通块，必定有一个点度为偶数（也就是原本与 u 相连的点）。

接着证明：不是 A 的状态，必定可以转化为状态 A。

这个其实也不难，我们容易想到，必定有一个度为偶数的点，它有一棵子树，里面的所有点，度数都是奇数。

事实上，如果一个点不行，就换另一个点，依次枚举即可找到。

这一部分的具体证明：其实特别简单。

第一次指定根时我们有一棵树，然后如果没有满足要求的子树的话，我们直接从下往上找到深度最大的度为偶数的点。

这个点既然深度最深，那它下面必定都是度为奇数的点。这一部分就证掉了。

那我们知道这个有什么用呢？更简单了，直接通过删除其他点，保留下这个根以及全是奇点的子树。那么根的度就会变成 1。剩下的其他点又都是奇点，那不就变成状态 A 了吗？

其实认真阅读上述内容，并不是很困难。如果不仔细证明的话，实际上几分钟就能想出以上两个结论。

有了这两个结论，接下来就很容易了吧。说白了就是：A 必须变成非 A，非 A 可以变成 A。

阅读题目，当对手将状态变为了 n = 1，你就赢了。n = 1 代表着：非 A 的状态。

也就是说，如果初始状态为非 A 状态，先手将这个状态变为 A 状态即可。对手很生气，因为他必须把这个状态再次变为非 A 状态。

由于每次 n 都会减少，而且先手每次都会获得一个非 A 状态。所以迟早这个状态会是 n = 1，于是先手获胜了。

反过来，先手获得了 A 状态，那么先手必须把这个状态变成非 A 状态。这下后手变成了先手，同上操作即可。后手获胜。

其实很简单，对吧？

完整代码

十分简单精简。

#include <iostream>
#include <cstdio>
using namespace std;
int in[100005];
void solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) in[i] = 0;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        in[u]++, in[v]++;
    }
    for (int i = 1; i <= n; i++)
        if (in[i] % 2 == 0) //度为偶数，先手必胜 
        {
            puts("Hifuu");
            return;
        }
    puts("Luna");
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

希望能帮助到大家！