【F 游戏】2020上海高校程序设计竞赛暨第18届上海大学程序设计联赛夏季赛（同步赛）解题报告

F 游戏

题目描述 Sparken 和 Cubercsl 喜欢玩游戏。这天他们从 Compute 那里得到了一棵有 n 个点的树（有 n-1 条边的连通图），于是他们决定利用这棵树来进行游戏。游戏规则是这样的：两个人轮流从树上选择一条边，对这条边两边所连接的点数较少的一边进行“收获”操作，并获得相同于所收获的点数的分数。在进行“收获”操作之后，对应边的一侧在之后的游戏中不再存在。特别的，如果两边的点数相同，可以任选一边“收获”。如果树上只剩下一个点，那么可以单独对这一个点进行“收获”。在双方都不能操作时，分数高者获胜。现在 Sparken 一如既往的得到了先手的权利。她想知道，如果他们都按照最优策略进行游戏，她是否能获胜。为了保证两人一定能分出胜负，保证 n 为奇数。

输入描述 第一行输入一个整数 T (1≤T≤10)，表示数据的组数。对于每组数据：第一行输入一个整数 n (1≤n≤19，n 为奇数)，表示树的点数。接下来 n-1 行，每行输入两个整数 u,v (1≤u,v≤n) 表示树的一条边。

输出描述 对于每一组数据，在一行输出一个字符串：如果 Sparken 可以获胜，输出 Yes，否则输出 No。

思路
容易证明，Sparken是必胜的。每个case直接输出Yes即可过题。
如果Cubercsl有一个更优解，那Sparken必然有机会先于Cubercsl完成这个解。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
template<class _T>inline void read(_T &_a)
{
    bool f=0; char _c=getchar(); _a=0;
    while(_c<'0'||_c>'9'){ if(_c=='-') f=1; _c=getchar(); }
    while(_c>='0'&&_c<='9'){ _a=(_a<<3)+(_a<<1)-'0'+_c; _c=getchar(); }
    if(f) _a=-_a;
}

int T;
 
int main()
{
    for(read(T);T;--T) printf("Yes\n");
    return 0;
}