P3177 [HAOI2015] 树上染色 题解

· · 个人记录

前言

传送门

看过《指南》的同学应该都有印象，与其说这道题是个多重背包，其实不如说它是个分组背包。

题目转化为个体贡献这个trick不加赘述，其它题解说的很清楚。其实我觉得只要理解了它是个分组背包，可以方便思考很多，也不会出现那么多问题。

正文

我们先给f[u][V]下精准定义：u所在子树内（包括u）黑点有V个时，该子树内所有边的贡献的最大值。

讲解答前要搞明白的一个幺蛾子：而我们转移时的决策其实是如何分配这V个黑点给各个子树（注意，u可能为黑点，当它为黑点的情况，应当是分配V-1个黑点）。我们不妨第一遍计算时，考虑分配V个点，计算完毕再将分配V-1个点的情况并到分V个点的情况中，这个trick类似《指南》中一道叫选课的例题。这里些许不一样因为我们算的是边的贡献，我们每次转移计算的其实是当前点与各儿子的连边的贡献。

如果幺蛾子看着有点懵，可以先看解答。为什么说它是分组背包？因为每一个子树就是一组，分配给这个子树多少黑点就是物品，这些物品显然是互斥的，因为每次决策你只能分给一个子树定值数量的黑点。那么根据分组背包的嵌套结构，最外层应是枚举每一组（即枚举每个儿子，这里肯定要递归，因为决策要用到儿子的结果），第二层应是倒序枚举容量（保证状态是由前一组转移过来的），第三层则是枚举物品。 下面是核心的dp函数：（f初始化为-1）

void dp(int u,int fa){
    sze[u]=1;
    f[u][0]=0;
    //边界注意，没有枚举组之前，只有分配0个黑点是合法的
    //注意，上文有提到，我这里的解法是先不分配u的颜色的，其实更有助于理解
    for(int i=head[u];i;i=e[i].nxt){//枚举每一组
        int v=e[i].to;
        if(v==fa) continue;
        dp(v,u);
        sze[u]+=sze[v];
        for(int V=min(k,sze[u]);V>=0;V--){//倒序枚举容量
            for(int j=max(0LL,V-sze[u]);j<=min(V,sze[v]);j++){//每组只能选一个
                if(f[u][V-j]==-1) continue;//这句意义在于枚举前一组时f[u][V-j]不一定计算过，该情况不合法要跳掉
                f[u][V]=max(f[u][V],f[u][V-j]+f[v][j]+(j*(k-j)+(sze[v]-j)*(n-sze[v]-(k-j)))*e[i].d);
            }
        }
    }
    for(int V=min(k,sze[u]);V>=1;V--) f[u][V]=max(f[u][V],f[u][V-1]);//到这里再分配u的颜色
}