hdu 3094——A tree game

谁践踏了优雅 2022-07-15 08:56 238阅读 0赞

题意：

一颗树，然后两个操作，一是删除一条边，二是移除不与根相连的部分。

思路：

树上博弈的基础题目。

code：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int N=1e5+5;
  5. std::vector<int> v[N];
  6. int dfs(int u,int p){
  7.     int ans=0;
  8.     for (int i=0;i<v[u].size();i++){
  9.         int k=v[u][i];
  10.         if (k!=p){
  11.             ans^=(dfs(k,u)+1);
  12.         }
  13.     }
  14.     return ans;
  15. }
  16. int main(){
  17.     int T,n;
  18.     scanf("%d",&T);
  19.     while (T--){
  20.         scanf("%d",&n);
  21.         for (int i=0;i<=n;i++) v[i].clear();
  22.         for (int i=1;i<n;i++){
  23.             int x,y;
  24.             scanf("%d%d",&x,&y);
  25.             v[x].push_back(y);
  26.             v[y].push_back(x);
  27.         }
  28.         if (dfs(1,-1)) puts("Alice");
  29.         else puts("Bob");
  30.     }
  31. }

发表评论

表情：
评论列表 （有 0 条评论，238人围观）

还没有评论，来说两句吧...

相关阅读

    相关 HDU_2580 A simple stone game

    刚开始看这一题时，就知道这根本不是一道简单题（对当时没学K倍动态减法的我来说），因为前几天刚做完一道斐波那契额数列的博弈而且它仅仅是这道题k=2的一个特例而已-\_-|||。

    蔚落蔚落/ 0 赞/ 144 阅读

    相关 HDU 6241 Color a Tree

    题意：给你一棵树，然后让你对树上的节点进行黑白染色。然后染色有一些要求，对于A类要求，要求在x的子树中，至少有y个节点被染成了黑色；对于B类要求，要求在树的所有节点除了x以及

    ╰半夏微凉°╰半夏微凉°/ 0 赞/ 266 阅读

    相关 HDU(1851) A Simple Game (博弈)

    任给N堆石子,两人轮流从任一堆中任取(每次只能取自一堆),规定每方每次最多取K颗,取最后一颗石子的一方获胜.问先取的人如何获胜？ 巴什博奕和尼姆博弈的综合。 令Bi=Mi

    冷不防冷不防/ 0 赞/ 334 阅读