题目大意：

给定一棵n个结点的树

一开始黑方占据1号结点，白方占据n号结点

其他结点都没有颜色

每次黑方可以选择黑色结点临近的未染色结点，染成黑色

白方同理。

最后谁不能走谁输。

 

题解：

其实简单想想就可以想明白。

黑方肯定要往通往白方的最短路延伸，白方也是这样。

因为这样每次你可以最大化可行动次数。

所以先以1为根，dfs一遍，然后找到路径。

模拟一下走路径的过程，路径走光了就比谁的可行动次数多（有点像围棋的气的感觉），输出结果就可以了

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 1e5 + 100;vector
         
           G[maxn];int deep[maxn], sz[maxn], f[maxn];deque
          
            Q;void dfs(int x, int fa, int d){ deep[x] = d; sz[x] = 1; f[x] = fa; for(auto to : G[x]){ if(to == fa) continue; dfs(to, x, d+1); sz[x] += sz[to]; }}int main(){ int n, x, y; cin>>n; for(int i = 1; i < n; i++){ scanf("%d %d", &x, &y); G[x].push_back(y); G[y].push_back(x); } dfs(1, 1, 1); x = n; while(x != 1){ Q.push_back(x); x = f[x]; } Q.push_back(1); int ansB = 0, ansW = 0, B = 0, W, temp; while(1){ if(Q.empty()){ ansB += sz[B]-1-sz[W]; ansW = sz[W] - ansW; if(ansB <= ansW) cout<<"Snuke"<