点分治+SG函数还真是令人意外的组合啊
思路
这道题看到找一条满足条件的链，想到点分治
看到博弈，想到SG函数
然后就变成一道SG函数+点分治的题了
然后1e9的SG函数怎么搞？当然是打表了
然后各种出锅
- 多组数据记得清零
- SG函数不要打错表QwQ
因为对着租酥雨julao的blog调了好久，所以代码极其相似
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;
int T,n,s,k,fir[30100],nxt[30100<<1],u[30100<<1],v[30100<<1],cnt,root,sz[30100],f[30100],vis[30100],ass=0,Siz,w_p[30100],tp_val;
unordered_map<int,int> S;
void addedge(int ui,int vi){
cnt++;
u[cnt]=ui;
v[cnt]=vi;
nxt[cnt]=fir[ui];
fir[ui]=cnt;
}
int SG3(int x){//k==3 时 , SG[x]=floor(x/k)
return x/s;
}
int SG1(int x){//k==1 时 , SG[x]=x
return x;
}
int SG2(int x){
if((x+1)%(s+1)==0)
return 2;
else
return x%2;
}
int SG4(int x){
if(!x)
return 0;
if(x%4==1||x%4==2)
return x;
if(x%4==3)
return x+1;
else
return x-1;
}
int SG(int x){
if(k==1)
return SG1(x);
else if(k==2)
return SG2(x);
else if(k==3)
return SG3(x);
else if(k==4)
return SG4(x);
else
return 0;
}
void findroot(int u,int fa){
sz[u]=f[u]=1;
for(int i=fir[u];i;i=nxt[i]){
if(vis[v[i]]||v[i]==fa)
continue;
findroot(v[i],u);
sz[u]+=sz[v[i]];
f[u]=max(f[u],sz[v[i]]);
}
f[u]=max(Siz-sz[u],f[u]);
if(f[u]<f[root] || !root)
root=u;
}
void queryhas(int u,int fa,int d){
if(S[d^tp_val])
ass=1;
for(int i=fir[u];i;i=nxt[i]){
if(v[i]==fa||vis[v[i]])
continue;
queryhas(v[i],u,d^w_p[v[i]]);
}
}
void getxor(int u,int fa,int d){
S[d]++;
for(int i=fir[u];i;i=nxt[i]){
if(v[i]==fa||vis[v[i]])
continue;
getxor(v[i],u,d^w_p[v[i]]);
}
}
void divide(int u){
vis[u]=true;
S[0]++;
tp_val=w_p[u];
for(int i=fir[u];i;i=nxt[i]){
if(vis[v[i]])
continue;
queryhas(v[i],0,w_p[v[i]]);
getxor(v[i],0,w_p[v[i]]);
}
S.clear();
for(int i=fir[u];i;i=nxt[i]){
if(vis[v[i]])
continue;
Siz=sz[v[i]];
root=0;
findroot(v[i],0);
divide(root);
}
}
// void SG(int s){
// for(int i=1;i<=90;i++){
// memset(barrel,0,sizeof(barrel));
// for(int j=1;j<=i;j++){
// barrel[sg[i-j]]=true;
// }
// for(int j=1;j<i;j++){
// barrel[sg[j]^sg[i-j]]=true;
// }
// for(int j=0;j<=10000-1;j++)
// if(!barrel[j]){
// sg[i]=j;
// break;
// }
// }
// }
int main(){
#ifndef ONLINE_JUDGE
freopen("t.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
memset(fir,0,sizeof(fir));
memset(nxt,0,sizeof(nxt));
memset(vis,0,sizeof(vis));
cnt=0;
ass=0;
S.clear();
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
int a,b;
scanf("%d %d",&a,&b);
addedge(a,b);
addedge(b,a);
}
for(int i=1;i<=n;i++)
scanf("%d",&w_p[i]);
scanf("%d",&k);
if(k==2||k==3)
scanf("%d",&s);
for(int i=1;i<=n;i++)
w_p[i]=SG(w_p[i]);
root=0;
Siz=n;
findroot(1,0);
divide(root);
if(ass)
printf("Mutalisk ride face how to lose?\n");
else
printf("The commentary cannot go on!\n");
}
return 0;
}