Description
有一颗N个节点的树，其中1号节点是整棵树的根节点，而对于第i个点(2≤i≤N)，其父节点为Pi 对于这棵树上每一个节点Snuke将会钦定一种颜色（黑或白），以及一个非负整数的点权。 Snuke有一个他最喜欢的整数序列，X1,X2,…,XN，他希望能够钦定这些点的点权和颜色。使得: 对于每一个点i，都满足i的整颗子数内所有和i颜色相同的点(包括i本身)的点权和恰好为Xi。 现在给定你这棵树的结构和Snuke最喜欢的整数序列，请你判断是否有一种钦定的方案使得其满足上文所述的条件
Input
第一行一个正整数N表示点的数量。 第二行N−1个正整数，其中第i个数表示编号为i+1的点的父节点编号。 第三行N个非负整数，表示Snuke最喜欢的整数序列。
Output
如果存在一种可行方案，则输出"POSSIBLE"； 否则，输出"IMPOSSIBLE" （不加引号）
Solution
以前没做过这种，被谔谔到。
树形DP。 设w[i]，b[i]分别为i为根的子树中两种颜色的权值和。 对于根为i的子树，其中一个颜色的权值总和为定值Xi，另外一种随便选，不妨令w[i]=Xi。 因为权值可以随便取，所以只需要保证i的子树(除去i)的一种颜色的权值和不大于Xi，剩下的都可以由i点补齐。 这里要尽量让一种颜色的权值和小，可以采取贪心思想，统计i的每个儿子j的min(w[i],b[i])的和。为什么可以取min？因为我们并没有定义真正的颜色，w和b只是区分两种颜色而非定义为黑白，所以我们可以随意翻转颜色。 同时，为了全局更优，还要使w[i]已经为Xi时，b[i]最小，即w[i]最大，i的权值最小。这里用一个背包来求，用w[j]和b[j]更新(j为i的儿子)。
Code
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
vector
<int>v
[1010];
int w
[1010],b
[1010],a
[1010],n
;
bool work(int x
){
if(!v
[x
].size()){
w
[x
]=a
[x
],b
[x
]=0;
return true;
}
ll sum
=0;
int dp
[5010]={0};
for(int i
=0;i
<v
[x
].size();i
++){
if(!work(v
[x
][i
])) return 0;
sum
+=w
[v
[x
][i
]]+b
[v
[x
][i
]];
}
ll mins
=0;
for(int i
=0;i
<v
[x
].size();i
++)
mins
+=min(w
[v
[x
][i
]],b
[v
[x
][i
]]);
if(mins
>a
[x
]) return false;
for(int i
=0;i
<=a
[x
];i
++) dp
[i
]=i
;
for(int i
=0;i
<v
[x
].size();i
++){
int y
=v
[x
][i
];
for(int j
=a
[x
];j
;j
--){
if(j
>=w
[y
]) dp
[j
]=min(dp
[j
],dp
[j
-w
[y
]]);
if(j
>=b
[y
]) dp
[j
]=min(dp
[j
],dp
[j
-b
[y
]]);
}
}
w
[x
]=a
[x
];
b
[x
]=sum
-(a
[x
]-dp
[a
[x
]]);
return 1;
}
int main(){
int x
;
scanf("%d",&n
);
for(int i
=2;i
<=n
;i
++){
scanf("%d",&x
);
v
[x
].push_back(i
);
}
for(int i
=1;i
<=n
;i
++)
scanf("%d",&a
[i
]);
if(work(1)) printf("POSSIBLE");
else printf("IMPOSSIBLE");
}
