[ARC083E]Bichrome Tree

ARC083E

一些性质：

• 答案与颜色无关，只与每对父子间的相对关系有关。
• 只要子树某种颜色的权值和小于等于要求，这个子树就一定能被满足。(不够就填上)
• 对于$i$的某部分子树，如果两种相对颜色的最小值均大于$X_ i$，那么$i$子树无解。
• 对于$x$的子树，如果一种相对颜色的值已经确定，另一种颜色的值越小越好。

现在考虑一个DP:
$dp[i][j]$表示以$i$ 为根的子树中，如果一种相对权值为$j$，另一种相对权值的最小值。
方程($hx[i]$表示题目要求的权值和)：
$dp[i][j]=min(dp[i][j],dp[i][j-hx[k]]+dp[k][hx[k]],dp[i][j-dp[k][hx[k]]+hx[k])(fa[k]==i)$
假如出现了上面第一条性质，那就无解了。

code:

#include<iostream>
#include<cstdio>
#include<cstring>
const int N=1002;

inline void apn(int &a,int b){
	if(a>b)a=b;
}

inline char get_c(){
	static char buf[20000],*h,*t;
	if(h==t){
		t=(h=buf)+fread(buf,1,20000,stdin);
	}
	return h==t?EOF:*h++;
}

inline int nxi(){
	int x=0;
	char c;
	while((c=get_c())>'9'||c<'0');
	while(x=x*10+c-48,(c=get_c())>='0'&&c<='9');
	return x;
}

int main(){
	static int fa[N],hx[N],dp[N][5002];
	int n=nxi();
	for(int i=2;i<=n;++i) fa[i]=nxi();
	for(int i=1;i<=n;++i) hx[i]=nxi();

	for(int x=n;x;--x){
		int y=fa[x];
		for(int i=hx[y];i>=0;--i){
			int p=dp[y][i];
			dp[y][i]=1e5;
			if(hx[x]<=i){
				dp[y][i]=(hx[x]?dp[y][i-hx[x]]:p)+dp[x][hx[x]];
			}
			if(dp[x][hx[x]]<=i){
				apn(dp[y][i],(dp[x][hx[x]]?dp[y][i-dp[x][hx[x]]]:p)+hx[x]);
			}
		}
	}
	puts(dp[1][hx[1]]>=1e5?"IMPOSSIBLE":"POSSIBLE");
	return 0;
}