AT3536 Bichrome Tree

dp 解题报告

---

题目链接

题目大意

现有一棵有 $n$ 个节点的树，根节点为 1，每个节点可以染成黑色或白色。
给出一个长度为 $n$ 的序列，分别为 $X_1,X_2,X_2\cdots X_n$，你可以将每个节点赋一个非负整数值，问是否能使以节点 $i$ 为根的子树中，与 $i$ 颜色相同的节点（包括 $i$ 本身）的权值和等于 $X_i$（$1 \sim n$ 中的每一个数都要满足）。

解题思路

一眼dp
看到这题后马上反应树型dp，然后……就没有然后了……

仔细想一下，其实这题在转移的时候并不用考虑把当前点染成哪种颜色，因为它和它的子节点的关系只有两种：颜色相同，颜色不同。 而两个子树的颜色是不会互相干扰的，所以，我们在dp时只需决定每个子节点的颜色是否与根节点相同，而无需考虑它要选那种颜色（相当于可以使整个子树的颜色翻转）。

那么，我们怎么样才能使节点的赋值情况尽量满足题目的要求（即如何做到最有决策）呢？
先考虑一下什么情况下是没办法满足要求的，
对于一个节点，它的每一个子节点都有两个值（白色和黑色），而对于每一个子节点，它都只能且必须选一个值，由于我们为节点赋的值必须是非负整数，所以如果节点 $u$ 所有的子节点的两个值中的较小值的和 $min\_sum > X_u$ 那么就无法满足题目的要求。
为了避免这种情况出现，我们就要使每个节点的值尽量地小。
设 $w_u$ 为节点 $u$ 的值，$sum$ 为节点 $u$ 的子树中（不包括它本身）与它颜色相同的点的权值和，可得出式子 $X_u=w_u+sum$，我们要使 $w_u$ 尽量地小，那么就要使 $sum$ 尽量地接近 $X_u$，即 $sum$ 为小于等于 $X_U$ 的最大值。
那么，我们的问题就转化为：
有 $k$ 个数，每个数有两个值 $a_i,b_i$，每个数必须且只能取一个值，求一个最优方案，使 $k$ 个数的权值之和小于等于定值 $S$，且最大。

枚举？$O(2^n)$……

貌似背包可以解决，但是我不会……

那看看还能不能进一步简化问题。

先想想对每个节点要进行的操作，

对于每一个节点 $u$，我们先要取它的每个子树的两个权值的较小值之和，看它是否小于等于 $X_u$，若满足的话，那我们就可以试着用每一个子树的较大值替换它的较小值，使 $sum$ 尽量接近 $X_u$，设子树 $i$ 的较大值和较小值分别为 $lar_i,les_i$，那么，若用子树 $i$ 的较大值替换它的较小值，对答案的贡献为 $lar_i-les_i$。
我们设 $tmp=X_u-sum\_min$，并将每棵子树 $i$ 的 $lar_i-les_i$ 存起来（设为 $box[i]$，那么我们的问题就转化为了：
有 $k$ 个数，在这 $k$ 个数中取任意个数，使它们的和尽量接近 $tmp$，
现在dp貌似就可做了，
设 $f[i][j]$ 为考虑到第 $i$ 位（且取第 $i$ 个数）取了 $j$ 个数的和的最大值（小于等于 $tmp$），转移方程为：

$$f[i][j]=max\{\ f[k][j-1]\ \} +box[i]$$
取个max就行了，
结果还是 $n^3$……
加个堆优化， $n^2log\ n$，
看眼数据范围

$1 \le N \le 1,000$

能过。

那么这道题的思路基本上就到位了，实现起来还是挺简单的，简单来说就是 dp 套 dp……

代码实现

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=1000+7;
int n,size[N],w[N];
int lst[N],nxt[N],to[N],tot;
void add(int x,int y){
    nxt[++tot]=lst[x];
    to[tot]=y;
    lst[x]=tot;
}
void init(){
    cin>>n;
    int fa;
    for(int i=2;i<=n;i++){
        scanf("%d",&fa);
        add(fa,i);
    }
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
}
bool run(int u){
    int sum=0,cnt=0,box[N];     // box数组一定要定义在函数内，不然会受到下一层递归的影响
    for(int i=lst[u];i;i=nxt[i]){
        int v=to[i];
        if(!run(v)) return 0;
        size[u]+=size[v];
        int les=min(w[v],size[v]-w[v]);
        int lar=max(w[v],size[v]-w[v]);
        sum+=les;
        box[++cnt]=lar-les;
    }
    if(sum>w[u]){ return 0; }
    sum=w[u]-sum; int maxn=0;
    sort(box+1,box+1+cnt);
    priority_queue<int> h[cnt+7];
    for(int i=1;i<=cnt;i++){
        if(box[i]>sum) break;
        for(int j=i;j>=1;j--){
            int tmp=0;
            if(!h[j-1].empty()) tmp=h[j-1].top();
            while(!h[j-1].empty()&&tmp+box[i]>sum){ h[j-1].pop();tmp=h[j-1].top(); }
            if(tmp+box[i]>sum) continue;
            h[j].push(tmp+box[i]);
            maxn=max(maxn,tmp+box[i]);
            }
    }
    size[u]+=sum-maxn;
    return 1;
}
int main(){
    //freopen("tree.in","r",stdin);
    init();
    if(run(1)) printf("POSSIBLE\n");
    else printf("IMPOSSIBLE\n");
    return 0;
}