首页 > > 程序设计 > C/C++ >

朋友（翻转树边权值比赛）——依然是思维

2020-04-12 16:00:26来源：博客园阅读 ()

朋友（翻转树边权值比赛）——依然是思维

思维我们只需看与根节点直接相连的边权权值是1的有几条，就可判断以该节点为根节点而开始游戏的胜者，奇数->先手胜偶数->后手胜。

B君在围观一群男生和一群女生玩游戏，具体来说游戏是这样的：
给出一棵n个节点的树，这棵树的每条边有一个权值，这个权值只可能是0或1。在一局游戏开始时，会确定一个节点作为根。接下来从女生开始，双方轮流进行操作。
当一方操作时，他们需要先选择一个不为根的点，满足该点到其父亲的边权为1; 然后找出这个点到根节点的简单路径，将路径上所有边的权值翻转（即0变成1，1 变成0 )。
当一方无法操作时(即所有边的边权均为0)，另一方就获得了胜利。
如果在双方均采用最优策略的情况下，女生会获胜，则输出“Girls win!”，否则输出“Boys win!”。
为了让游戏更有趣味性，在每局之间可能会有修改边权的操作，而且每局游戏指定的根节点也可能是不同的。
具体来说，修改边权和进行游戏的操作一共有m个，具体如下：
$∙$

“1 x y z ”表示将x和y之间的边的边权修改为z。
B君当然知道怎么做啦！但是他想考考你。
Input包含至多5组测试数据。
第一行有一个正整数，表示数据的组数。
接下来每组数据第一行，有二个空格隔开的正整数n,m，分别表示点的个数，操作个数。保证n,m< 40000。
接下来n-1行，每行三个整数x,y,z，表示树的一条边。保证1<x<n, 1<y< n, 0 <= z <= 1。
接下来m行，每行一个操作，含义如前所述。保证一定只会出现前文中提到的两种格式。
对于操作0，保证1 <= x <= n ;对于操作1，保证1 <= x <= n, 1 <= y <= n, 0 <= z <= 1，保证树上存在一条边连接x和y。
Output对于每组数据的每一个询问操作，输出一行“Boys win!”或者“Girls win!”。Sample Input

Sample Output

Boys win!
Girls win!
Girls win!
Boys win!
Girls win!
Boys win!
Boys win!
Girls win!
Girls win!
Boys win!
Girls win! 
思路：
对于这种类似的题，我们知道一定有隐藏的规律。
主要就是看直接连到根节点的树边。
①假如连接到根节点的边只有一条，我们把这条边叫作X。
　　1.那么我们想，如果X边权是1：
　　　　先手可以不管X后面的边，只将X翻成0，即使下一步，另一人将后面的可以翻边翻了，那么X又变成1了，这样不管另一人翻后面的哪条边，先手都可以只翻X，消耗另一人，直至X后面全是0，再翻X，先手胜利。
　　2.相反的，X边权是0：
　　   先手只能翻X后面的边，而另一人（后手）就可以仿照上一种情况的先手，后手取胜。
②类似的，我们将直接连接到根节点的，且边权是1的边拓展到多条，将它们统称为X：
　　1.如果X的数量是奇数，先手与后手（一条链一条链地）轮流消耗对方，最终一条带X的链还是先手先翻X，先手取胜（仿照①1.）
　　2.同理，X的数量是偶数，先手与后手（一条链一条链地）轮流消耗对方，最终一条带X的链是后手先翻X，后手取胜（仿照①2.）
　　注意：（在②中，我们不跟①一样讨论直接连到根节点的，边权是0的边，因为如果这条边后面的边有权值1，先手翻了之后，
　　这条直接连到根节点的边就成1了，后手就可以用其消耗对方，后手胜利，也就相当于X是0条的时候，即X数量是偶数，同②2.结论）
总结：
　　我们只需看与根节点直接相连的边权权值是1的有几条，就可判断以该节点为根节点而开始游戏的胜者，奇数->先手胜  偶数->后手胜。
代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn=4e4+3;
 7 int head[maxn],n,m,cnt,key;
 8 int x,y,z;
 9 struct Edge{bool wei;int to,next;}e[2*maxn];
10 void Add(int x,int y,int z){
11     e[++cnt].to=y;
12     if(z)e[cnt].wei=1;else e[cnt].wei=0;
13     e[cnt].next=head[x];
14     head[x]=cnt;
15 }
16 void Xiugai(int x,int y,int z){
17     for(int i=head[x];i;i=e[i].next){
18         if(y==e[i].to){
19             if(z)e[i].wei=1;else e[i].wei=0;
20             break;
21         }
22     }
23     for(int i=head[y];i;i=e[i].next){
24         if(x==e[i].to){
25             if(z)e[i].wei=1;else e[i].wei=0;
26             return;
27         }
28     }
29 }
30 void Sta(int root){
31     int ans=0;
32     for(int i=head[root];i;i=e[i].next){
33         if(e[i].wei)ans++;
34     }
35     if(ans%2==1)printf("Girls win!\n");
36     else printf("Boys win!\n");
37 }
38 int main(){
39 //    freopen("1.in","r",stdin);
40     int t;    
41     scanf("%d",&t);
42     while(t--){
43         cnt=0;memset(head,0,sizeof(head));
44         scanf("%d%d",&n,&m);
45         for(int i=1;i<n;++i){
46             scanf("%d%d%d",&x,&y,&z);
47             Add(x,y,z);Add(y,x,z);
48         }
49         for(int i=1;i<=m;++i){
50             scanf("%d",&key);
51             if(!key){
52                 scanf("%d",&x);
53                 Sta(x);
54             }else{
55                 scanf("%d%d%d",&x,&y,&z);
56                 Xiugai(x,y,z);
57             }
58         }
59     }
60     return 0;
61 }