朋友（翻轉樹邊權值比賽）——依然是思維

B君在圍觀一群男生和一群女生玩游戲，具體來說游戲是這樣的：
給出一棵n個節點的樹，這棵樹的每條邊有一個權值，這個權值只可能是0或1。 在一局游戲開始時，會確定一個節點作為根。接下來從女生開始，雙方輪流進行 操作。
當一方操作時，他們需要先選擇一個不為根的點，滿足該點到其父親的邊權為1; 然後找出這個點到根節點的簡單路徑，將路徑上所有邊的權值翻轉（即0變成1，1 變成0 )。
當一方無法操作時(即所有邊的邊權均為0)，另一方就獲得了勝利。
如果在雙方均採用最優策略的情況下，女生會獲勝，則輸出“Girls win!”，否則輸 出“Boys win!”。
為了讓游戲更有趣味性，在每局之間可能會有修改邊權的操作，而且每局游戲指 定的根節點也可能是不同的。
具體來說，修改邊權和進行游戲的操作一共有m個，具體如下：
∙“0 x”表示詢問對於當前的樹，如果以x為根節點開始游戲，哪方會獲得勝利。
∙

2
2 3
1 2 0
0 1
1 2 1 1
0 2
4 11
1 2 1
2 3 1
3 4 0
0 1
0 2
0 3
0 4
1 2 1 0
0 1
0 2
0 3
1 3 4 1
0 3
0 4

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的數量是奇數，先手與後手（一條鏈一條鏈地）輪流消耗對方，最終剩下一條權值是1的X，還是先手先翻X，先手取勝（仿照①1.）
　　2.同理，X的數量是偶數，先手與後手（一條鏈一條鏈地）輪流消耗對方，最終剩下一條權值是1的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 }