题解：CF1363C Game On Leaves

· · 题解

CF1363C Game On Leaves题解

题目大意

给定一颗无向无根树，每次操作可以删去一个叶子结点。
给定一个特殊节点，先删除这个节点的人赢，假定两个人使用最优策略，问是先手赢还是后手赢。

分析

必胜态：当 n \le 2 或特殊节点为叶子节点时，必胜。
必败态：当 n = 3 且特殊节点不为叶子结点时，必败。因为此时删除任意一个节点，必定会进入到 n = 2 时的必胜态，所以此时先手必败。
所以我们只需要判断 n - 3 的奇偶性，为奇数则后手赢，否则先手赢。
这部分代码如下：

if(n <= 2 || d[x] == 1)//d是每个节点的度数
    cout << "Ayush" << endl;
else
    cout << ((n - 3) % 2 == 0 ? "Ashish" : "Ayush") << endl;//这里用到了三目运算符，格式为 A ? B : C，如果 A 为真，则执行 B，否则执行 C

有没有其它情况？
肯定没有。
我们先假设特殊节点为根节点。如果第一个人删除某节点后，特殊节点为叶子结点，那么此时第一个人必败，又因为两人都使用的是最优策略，所以不会出现这种情况。