洛谷P8347 「Wdoi-6」另一侧的月题解

题意：

给定 \(n\) 个节点的树（保证 \(n\ge 2\)），Hifuu 和 Luna 交替操作，前者先手。每回合操作者选择一个节点，将「该节点」和「所有与该节点相连的边」删除，形成若干个连通块，操作者再从中保留一个连通块。如果该回合结束后只剩下一个节点，则该回合的操作者失败，另一个人胜利。问谁存在必胜策略。

输入格式：

本题多组数据。第一行输入一个正整数 \(T\)，表示数据组数。对于每一组数据：

第一行有一个正整数 \(n\)。

接下来 \(n-1\) 行，每行两个正整数 \(u_i,v_i\)。表示一条连接节点 \(u_i\) 和 \(v_i\) 的双向的灵能输送渠道。

输出格式：

对于每一组数据，输出莲子和梅莉是否能够到达月之都。具体而言，若她们存在必定能到达月之都的策略，则输出 \(\texttt{Hifuu}\)，否则输出 \(\texttt{Luna}\)。

数据范围：

\(1 \leq T \leq 5\)，\(2 \le n \le 10^5\)，输入数据构成一棵树。

考虑较小情况时先手是否必胜。显然，一个点是必胜的，两个点是必败的，三个点又是必胜的。

有意思的是，当点变成 \(4\) 个的时候，菊花图是必败的，而链是必胜的。这俩的唯一区别就在于点的度数不同。

于是我们大胆猜测：任意状态先手必败当且仅当所有点的度数均为奇数。

证明记所有点的均为奇点的状态为 \(\rm P\) ，相对应的记存在至少一个偶点的状态为 \(\rm N\) 。

显然我们只需证明 \(\rm P\) 的后继全为 \(\rm N\) ，且 \(\rm N\) 存在至少一个后继为 \(\rm P\) 即可。

注意到题目中的切法实际上只是删除了某一条边，并且选择它的某一侧作为后继状态。

对于 \(\rm P\) 态，切一条边会使两个点变成偶点，无论留哪个都会变为 \(\rm N\) 。

对于 \(\rm N\) 态，由于偶点的个数有限，故随意钦定一个根后必有一棵子树只有根节点是偶点，

选择这棵子树作为后继（也就是切它到父节点的边），可以得到 \(\rm P\) 的后继。\(\square\)

因此我们只需要判一下有没有偶点即可。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

int d[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq;
    while(qwq--)
    {
        int n, ok = 0; cin >> n; rep(i, 1, n) d[i] = 0;
        rep(i, 1, n - 1) { int u, v; cin >> u >> v; ++d[u]; ++d[v]; }
        rep(i, 1, n) if(!(d[i] & 1)) { cout << "Hifuu\n"; ok = true; break; }
        if(!ok) cout << "Luna\n";
    }
    return 0;
}

参考文献：

[1] https://www.luogu.com.cn/article/59tk349y

题外话：

「人类的梦想之一，月面旅行对一般人也终于成为可能！」
「从下个月起日本各个旅行公司将开始展开旅行」

然而，月球的表面，有着将月之都与荒凉的无生命星球隔开的一道结界。只要这道结界存在，人们只能看到石头罢了。

而月面旅行的费用，也绝不是身为大学生的莲子与梅莉二人所能承担的。但是，她们想要探寻的是，被结界所包裹的，有着高度发达文明的月之都。

这，便是另一侧的月。梅莉她看见了。兔子在捣药，身着华美的服装，优雅地在天空中起舞的天女。

「我说莲子啊。如果月面旅行太贵实在不行的话，我们要不要试着想点别的办法去月球呢？」