题解与讨论区 1224: 下围棋

题解与讨论区 1224: 下围棋

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

返回问题页面

题目描述

小姜在和miaoyao下围棋,由于在19X19的棋盘上面小姜总是输给miaoyao,于是他们是在一个有根树(根为1号节点,编号1-n)上面下围棋,围棋的规则也和我们日常说的规则不同。


规则如下:小姜和miaoyao轮流下棋,小姜执黑miaoyao执白,每次落子在一个树上面的合法节点,一个节点是合法节点仅当满足
1.该节点之前没有棋子
2.该节点不能是根节点(1号节点)
3.该节点到根的路径上面没有其他棋子


当某一方无法落子的时候,这一方输掉游戏。显然,如果场面上面存在合法的节点,轮到这个人时他必须落子。(不能pass)

第1224题的题解

特种幽灵

三月的狮子 的题解


本题需要一个SG函数的前置知识

于是
对于每一个子树的SG函数,就是子树的子树的SG函数亦或和+1
因为每一个子树都是一个石头游戏

所以就好了,这题非常简单,为啥没人做呢。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=1000005;
  4. vector<int>G[maxn];
  5. int dfs(int u,int fa){
  6. int sg=0;
  7. for(auto to:G[u]){
  8. if(to==fa)continue;
  9. sg^=dfs(to,u);
  10. }
  11. return sg+1;
  12. }
  13. int main(){
  14. int t;
  15. scanf("%d", &t);
  16. while(t--){
  17. int n;
  18. scanf("%d", &n);
  19. for(int i=1;i<=n;i++)G[i].clear();
  20. for(int i=0;i<n-1;i++){
  21. int u,v;
  22. scanf("%d%d", &u, &v);
  23. G[u].push_back(v);
  24. G[v].push_back(u);
  25. }
  26. int ans=dfs(1,0)-1;
  27. if(ans==0)
  28. printf("YES\n");
  29. else
  30. printf("NO\n");
  31. }
  32. }



点赞 1
举报