T2
分析见代码
#pragma GCC optimize(2) #include<bits/stdc++.h> #define pass puts("pass") #define LL long long #define N 20 #define M 1000 using namespace std; int n; int fa[N]; int a,s,k,v; int f[N][N]; int flag[1<<17]; void dfs(int x) { if(v==a) {//满足条件退出 cout<<k<<endl; exit(0); } if(x==k) return; for(int i=1; i<=n; i++) {//枚举选点 v^=f[i][k-x]; if(x<flag[v]) {//记忆化搜索 flag[v]=x; dfs(x+1); } v^=f[i][k-x]; } dfs(x+1);//不标记点 } int main() { cin>>n; for(int i=2; i<=n; i++) cin>>fa[i];//输入爸爸 for(int i=1; i<=n; i++) { cin>>s; a=a*2+s;//输入最终状态,转为2进制 } //求标记第i个点j秒后会影响的点(2进制) for(int i=1; i<=n; i++) { int x=i; for(int j=1; j<=n; j++) { if(x)//特判 x为0不会影响点 f[i][j]=f[i][j-1]|(1<<(n-x)); else f[i][j]=f[i][j-1]; x=fa[x];//向上移 } } for(k=0; k<=n; k++) {//迭代加深 memset(flag,10,sizeof(flag)); dfs(0); } puts("frog"); return 0; }