【AtCoder Regular Contest 083 E】Bichrome Tree | Mrsrz's blog

贪心，构造。

题目大意：

给定一棵 $n$ 个结点的有根数，每个结点有一个数值 $X_i$。

现在要求把结点染成黑白两种颜色，并对每个结点指定一个权值 $a_i$。

要求满足：$i$ 的子树中和 $i$ 同色结点的权值和恰好是 $X_i$.

问是否有合法方案。

题解：

考虑从下往上依次确定。

确定一个结点的权值时，它的每个儿子结点都有两种不同的权值可以使用。我们无需管它到底是黑点还是白点，因为把整棵子树颜色翻转后还是合法。

对于一棵子树，其中一个权值一定是根结点。我们希望另外一个权值尽可能小，这样才能匹配更多的权值。

在每层处做一个背包问题即可得出所有可能的不包括根的子树和。

我们要传上去的尽可能小，就是要使花费的尽可能大，所以找一个比 $X_i$ 小，且能得到的权值和 $v$，令 $a_i=X_i-v$ 即可。

如果某次找不到，则说明无解。

Code：

#include<cstdio>
#include<bitset>
#include<vector>
#include<cstdlib>
using namespace std;
const int N=1145;
int n,fa[N],X[N],a[N];
vector<int>G[N];
bitset<5001>b;
void dfs(int now){
    int sum=0;
    for(int to:G[now])dfs(to),sum+=a[to];
    b.reset();
    b.set(0);
    for(int to:G[now])b=(b<<X[to])|(b<<(a[to]-X[to]));
    int x=-1;
    for(int i=X[now];~i&&x==-1;--i)if(b.test(i))x=i;
    if(x==-1)exit(puts("IMPOSSIBLE")*0);
    a[now]=sum+X[now]-x;
}
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;++i)
        scanf("%d",fa+i),G[fa[i]].push_back(i);
    for(int i=1;i<=n;++i)scanf("%d",X+i);
    dfs(1);
    puts("POSSIBLE");
    return 0;
}