题目传送门（内部题114）

输入格式

　　第一行一个正整数$n$。
　　接下来一行$n-1$个正整数，第$i$个数为$f_{i+1}$。
　　接下来一行$n$个数，若第$i$个数为$0$则表示林先森希望$i$号点的彩灯是关闭状态，若第$i$个数为$1$则表示林先森希望$i$号点的彩灯是开启状态。

输出格式

　　输出一行一个整数，表示林先森最少需要几秒才能看到他期望看到的树。

样例

样例输入1：

4
1 2 3
0 1 1 0

样例输出1：

2

样例输入2：

7
1 1 2 2 3 3
0 1 1 1 0 0 1

样例输出2：

3

数据范围与提示

样例解释：

　　第一个样例：
　　$\bullet$第一秒林先森拨动$3$号点的开关，彩灯状态变为$0\ 0\ 1\ 0$。
　　$\bullet$第二秒林先森什么也不做，彩灯状态变为$0\ 1\ 1\ 0$，满足要求。
　　第二个样例：
　　$\bullet$第一秒林先森拨动$4$号点的开关，彩灯状态变为$0\ 0\ 0\ 1\ 0\ 0\ 0$。
　　$\bullet$第二秒林先森拨动$7$号点的开关，彩灯状态变为$0\ 1\ 0\ 1\ 0\ 0\ 1$。
　　$\bullet$第三秒林先森拨动$1$号点的开关，与$2$号点传递的拨动效果抵消，彩灯状态变为$0\ 1\ 1\ 1\ 0\ 0\ 1$，满足要求。

数据范围：

　　对于$30\%$的数据，$n\leqslant 8$。
　　对于另$30\%$的数据，林先森希望看到所有彩灯都被点亮。
　　对于$100\%$的数据，$1\leqslant n\leqslant 16$。

题解

数据范围较小，考虑状压$DP$。

因为答案最大为$n$，所以我们可以枚举秒数。

设$dp[i][state]$表示第$i$秒，状态为$state$是否可行。

因为开关只与正负是否相同有关，而与具体是开还是关无关，所以我们可以假设最终的状态为起始状态，然后想办法转移到$0$状态（其实就是代码复杂度低一点而已）。

预处理出来每个点会对其它的点在下一秒做的贡献即可。

时间复杂度：$\Theta(2^nn^2)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,state;

int fa[20],Map[20][20];

bool dp[20][100000];

int main()

{

	scanf("%d",&n);

	for(int i=0;i<=n;i++)Map[1][i]=1;

	for(int i=2;i<=n;i++)

	{

		Map[i][0]=1<<(i-1);

		scanf("%d",&fa[i]);

		int now=i;

		for(int j=1;j<=n;j++)

		{

			now=fa[now];

			if(now)Map[i][j]=Map[i][j-1]|(1<<(now-1));

			else Map[i][j]=Map[i][j-1];

		}

	}

	for(int i=1;i<=n;i++){int x;scanf("%d",&x);state|=x<<(i-1);}

	dp[0][state]=1;

	for(int i=0;i<=n;i++)

	{

		if(dp[i][0]){printf("%d",i);break;}

		for(int s=1;s<(1<<n);s++)

			if(dp[i][s])

			{

				dp[i+1][s]=1;

				for(int j=1;j<=n;j++)

					dp[i+1][s^Map[j][i]]=1;

			}

	}

	return 0;

}

rp++