Problem Statement

A tree with (n) nodes has two weights (a) and (b) per node, initailly set to (0). At each step, you can toggle the (b) value of at most one node. For nodes with (b = 1), their (a) values are toggled, followed by toggling thier (b) values and their parent's (b) values (if the parent exists). The goal is to determine the minimum steps required to reach a target state for ({a_n}).

Approach

We use a dynamicc programming (DP) approach where time is the first dimension, and the state is represented as a bitmask. The DP checks feasibility at each time step, reducing the state space by leveraging the problem's constraints.

Code Example

#include<bits/stdc++.h>
#define N 20
#define M (1<<16)
using namespace std;
int read(){
    int x=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*w;
}
int n,fa[N],S[N][N];
bool f[N][M];int state;
int main(){
    n=read();
    for(int i=2;i<=n;i++)fa[i]=read();
    for(int i=1;i<=n;i++)
        for(int j=1,k=i;j<=n;j++,k=fa[k])
            S[i][j]=S[i][j-1]^(k?(1<<(k-1)):0);
    for(int i=1;i<=n;i++)
        if(read())state|=(1<<(i-1));
    f[1][0]=true;
    int lim=(1<<n);
    for(int i=1;i<=n;i++){
        if(f[i][state]){
            printf("%d\n",i-1);
            exit(0);
        }
        for(int s=0;s<lim;s++){
            if(!f[i][s])continue;
            f[i+1][s]=true;
            for(int j=1;j<=n;j++)
                f[i+1][s^S[j][i]]=true;
        }
    }
    return 0;
}