Description：

给定含 $n$ 个点的树,和每个点的限制 $x_i$ ，给每个点赋予一个颜色(黑白)和权值，满足对于每个点 $v$ ，子树 $v$ 中和 $v$ 同色的点的权值和等于 $x_v$ ，是否有解。

$1\le N \le 1000$

Solution：

首先发现如果存在一种方案使一个点的子树中所有与他颜色相同的点的点权和小于 $x_v$ ，那么一定可以通过调整这个点的点权得到一种可行的方案，而在处理完以 $k$ 为根的子树后，子树 $k$ 中与 $k$ 颜色相同的点权和一定为 $x_k$ ，于是设计状态为 $f[k]$ 表示以 $k$ 为根的子树中与 $k$ 颜色不同的点权和最小是多少，发现颜色可以互换，只要知道相对颜色即可，所以不用在状态里记录颜色。

转移时枚举每个子树的颜色跑背包：

设 $g[k][i]$ 表示前 $k$ 个子树某一种颜色权值和为 $i$ 时另一种颜色权值最小是多少。

这样即可得出最小解，再判断是否小于 $x_k$

注意转移顺序，把所有子树 $DP$ 完再处理当前节点。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 1010

int f[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int x[MAXN];

int g[2][MAXN * 5];

int fa[MAXN];

void dp(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(fa[k] == e[i].to)continue;

		fa[e[i].to] = k;

		dp(e[i].to);

	} 

	memset(g[0],0x3f,sizeof(g[0]));

	int cur = 0;

	g[cur][0] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(fa[k] == e[i].to)continue;

		cur = cur ^ 1;

		memset(g[cur],0x3f,sizeof(g[cur]));

		for(int j = 0;j <= x[k];++j)

		{

			if(j >= f[e[i].to])g[cur][j] = min(g[cur][j],g[cur ^ 1][j - f[e[i].to]] + x[e[i].to]);

			if(j >= x[e[i].to])g[cur][j] = min(g[cur][j],g[cur ^ 1][j - x[e[i].to]] + f[e[i].to]);

		}

	}

	for(int i = 0;i <= x[k];++i)

	{

		f[k] = min(f[k],g[cur][i]);

	}

	return;

}

int main()

{

	scanf("%d",&n);

	int a;

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

	{

		scanf("%d",&a);

		add(a,i);

	}

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

	{

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

	}

	memset(f,0x3f,sizeof(f));

	dp(1);

	if(f[1] < 0x3f3f3f3f)puts("POSSIBLE");

	else puts("IMPOSSIBLE");

	return 0;

}