F游戏

题目：
https://ac.nowcoder.com/acm/contest/6871/F
先上代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t=0;
    cin>>t;
    while(t--)
    {
        cout<<"Yes"<<endl;
    }
    return 0;
}

对，很显然这个游戏先手一定能赢。本人比赛的时候没有直接想到这一点，画了半天，没有什么思路，就干脆胡乱提交一发，居然AC了。。
这里简单给证明一下吧

这个图是树，所以任何一条边都是分割边（或，桥）。所谓分割边，是指去掉这条边后，图变为不连通（严格来说是连通分支变多，对于连通图来说，这等价于图变为不连通）。
设甲先手，乙后手。甲第i步面临的局面是图A，乙第i步面临的局面是图B，则B是A的子图。
设甲第i步的最优决策是选取边d，将A分为Q和P两部分，分别有q和p个顶点，q<=p，最大收益为a，则a=q。
设甲第i步的最优决策是选取边e，将B分为S和R两部分，分别有s和r个顶点，s<=r，最大收益为b，则b=s。
下证：a>=b
若不然，b>a，考虑图A中d和e的关系，共有2种情况：

• 1
  A = Q——P
  = Q——B
  = Q——S——R
  这种情形，甲在第i步的决策（选取d）不是最优决策。若选择e，有2种情况：
  一，R更少，收益a'=r>=s=b>a，矛盾
  二，Q——S更少，收益a'=q+s=a+s>a，矛盾
• 2
  A = Q——P
  = Q——B
  = Q——R——S
  这种情形，甲在第i步的决策仍不是最优的。若选择e，由s<=r<q+r可知，甲的收益a'=s=b>a。矛盾

所以a>=b。
甲先手，所以甲的行动步数不会少于乙，而每次行动，甲的收益不低于乙，所以甲不会输。很显然题目保证了不会平局，所以甲能赢。