参见BZOJ并行博弈。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #define maxv 40050 #define maxe 80050 using namespace std; int t,n,m,x,y,z,w,val[maxv]; map <int,int> mp[maxv]; void work() { memset(val,0,sizeof(val)); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) mp[i].clear(); for (int i=1;i<=n-1;i++) { scanf("%d%d%d",&x,&y,&z); val[x]^=z;val[y]^=z;mp[x][y]=mp[y][x]=z; } for (int i=1;i<=m;i++) { scanf("%d",&x); if (!x) {scanf("%d",&y);if (val[y]) printf("Girls win! ");else printf("Boys win! ");} else { scanf("%d%d%d",&y,&z,&w); if (mp[y][z]==w) continue; val[y]^=1;val[z]^=1;mp[y][z]^=1;mp[z][y]^=1; } } } int main() { scanf("%d",&t); for (int i=1;i<=t;i++) work(); return 0; }