[AtCoder Regular Contest 083] Bichrome Tree

树形DP。

每个点有两个属性：黑色点的权值和，白色点权值和，一个知道另一个也一定知道。

因为只要子树的和它相等的点得权值和不超过x[u]，u点的权值总能将其补齐。

设计状态f[u]表示以u为根的子树，和u颜色不同的最小权值和，树形背包转移。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int N=1005;

struct Edge{

	int to,nxt;

}e[N<<1];

int n,x[N],head[N],ecnt,f[N],g[2][5005];

void add(int bg,int ed){e[++ecnt].nxt=head[bg];e[ecnt].to=ed;head[bg]=ecnt;}

void dfs(int u) {

	for(int i=head[u];i;i=e[i].nxt) dfs(e[i].to);

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

	int cur=0;

	g[cur][0]=0;

	for(int i=head[u];i;i=e[i].nxt) {

		int v=e[i].to;cur^=1;

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

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

			if(j-x[v]>=0) g[cur][j]=min(g[cur^1][j-x[v]]+f[v],g[cur][j]);

			if(j-f[v]>=0) g[cur][j]=min(g[cur^1][j-f[v]]+x[v],g[cur][j]);

		}

	}

	for(int i=0;i<=x[u];i++) f[u]=min(f[u],g[cur][i]);

}

int main() {

	scanf("%d",&n);

	for(int i=2,p;i<=n;i++) scanf("%d",&p),add(p,i);

	for(int i=1;i<=n;i++) scanf("%d",&x[i]);

	memset(f,0x3f,sizeof f);

	dfs(1);

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

	else puts("IMPOSSIBLE");

	return 0;

}

巴特西

[AtCoder Regular Contest 083] Bichrome Tree

最新文章

热门文章