5163 -- 【11.04题目】玩游戏

Description

　　小A得了忧郁综合症，小B正在想办法开导她。

　　机智的小B决定陪着小A玩游戏，他从魔法的世界里变出一张无向联通图，每条边上都有边权。小B定义一条路径的权值为所有经过边中的最大权值，小A则定义两点的最短路径为所有路径中权值最小的路径权。

　　每次小A先选出两个点m1,m2，然后小B选出两个点b1,b2，计算出它们的最短路径m,b，然后小B会拿出两堆灵魂宝石，一堆有m个，另一堆有b个。然后小A先从一堆中选出若干个灵魂宝石拿走，接下来小B重复同样的操作，如此反复，直到取走最后一颗灵魂宝石，然后取走最后一颗宝石的人获胜。

　　小B认为这样游戏太简单，于是他会不定期向这张图上加上一些边，以增大游戏难度。

　　小A具有预知未来的能力，她看到了自己和小B在未来游戏中的选择，以及小B增加的边。现在对于每次游戏，小A想知道自己是否存在必胜的方法。但是预知未来已经消耗了她太多精力，出于疲惫她只好找到了你。

Input

　　第一行两个数N和M，表示这张无向图初始的点数与边数；

　　接下来M行，每行三个数u,v,q，表示点u和点v之间存在一条权值为q的边；

　　接下来一行一个数Q，表示操作总数；

　　接下来Q行，表示操作，每行格式为下面两条中的一条：

　　1.add u v q：表示在u与v之间加上一条边权为q的边；

　　2.game m1 m2 b1 b2：表示一次游戏，其中小A的选择点m1,m2，小B的选择点b1,b2。

　　数据保证1≤u,v,m1,m2,b1,b2≤n，1≤q，m1≠m2 且 b1≠b2

Output

　　对于每个game输出一行，若小A存在必胜策略，则输出“madoka”，否则输出“Baozika”，以回车结尾

Sample Input

5 6 1 2 3 2 3 6 4 2 4 5 3 5 3 4 5 5 1 5 4 game 1 3 4 3 game 1 5 2 4 add 2 5 4 game 1 5 3 4

Sample Output

Baozika madoka madoka

Hint

 

 

 

我们先求出一个最小生成树，然后每加上一条边我们就重新dfs一遍维护

至于那个博弈实际上就是一个nim博弈，直接异或起来判断是否是0就可以了

code：

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #define N 500005  7 using namespace std;  8 long long n,m;  9 struct node { 10     long long u,v,w,used; 11 } e[N],t[N]; 12 int first[N],nxt[N],cnt; 13 inline void add(long long u,long long v,long long w,long long d) { 14     e[++cnt].u=u; 15     e[cnt].v=v; 16     e[cnt].w=w; 17     e[cnt].used=d; 18     nxt[cnt]=first[u]; 19     first[u]=cnt; 20 } 21 inline bool cmp(const node&a,const node&b) { 22     return a.w
           
            =0; i--) { 56 if(dep[f[x][i]]>=dep[y]) { 57 if(max0
            
             =0; i--) { 68 if(f[x][i]==f[y][i])continue; 69 if(max0
             
              >k;147 if(k=="add") {148 long long u,v,w;149 u=read(),v=read(),w=read();150 T temp=lca(u,v);151 if(temp.max>w) {152 e[temp.id].used=0;153 // cout<
              <<" "<
               
                <<" u->"<
                
                 <<" v->"<
                 
                  <<" max->"<
                  
                   <<'\n';154 if(e[temp.id+1].u==e[temp.id].v&&e[temp.id+1].v==e[temp.id].u) {155 e[temp.id+1].used=0;156 } else e[temp.id-1].used=0;157 add(u,v,w,1);158 add(v,u,w,1);159 build();160 }161 } else {162 long long a,b,c,d;163 a=read(),b=read(),c=read(),d=read();164 long long max1=lca(a,b).max,max2=lca(c,d).max;165 // cout<<"max1->"<
                   
                    <<" max2->"<
                    
                     <<" "<<'\n';166 if(max1^max2) {167 cout<<"madoka"<<'\n';168 } else {169 cout<<"Baozika"<<'\n';170 }171 }172 }173 return 0;174 }
                    
                   
                  
                 
                
               
             
            
           
          
         
        
       
      

over