P3177 [HAOI2015] 树上染色

树上背包。

从前，我一直认为树上背包是 $\mathcal O(n^2m)$ ，直到这道题，才知道树上背包可以做到 $\mathcal O(nm)$ 的qwq。。。

状态很明显是 $f_{x,i}$，表示在 $x$ 为根的子树中选取 $i$ 个黑点得到的最大贡献。很明显我们不能直接计算，而是应该计算每条边的贡献，计算每条边被路径覆盖的次数并乘上其长度。

考虑覆盖次数。 $cnt=k\times (m-k)+size_y\times (n-m-(size_y-k))$，表示 $x$ 的儿子 $y$ 中选取 $k$ 个黑色节点时，$(x,y)$ 的覆盖次数，这很容易理解。然后就树上背包即可。

注意需要先转移 $k=0$ 的状态。还有需要注意不可行的状态，判一下边界即可。

Code

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=2e3+10,M=4e3+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m;
int tot,head[N],ver[M],e[M],ne[M];
int si[N];
ll f[N][N];
inline void add(int u,int v,int w)
{
    ver[++tot]=v;
    e[tot]=w;
    ne[tot]=head[u];
    head[u]=tot;
}
void dfs(int x,int fa)
{
    si[x]=1;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,x);
        for(int j=min(si[x]+si[y],m);~j;j--)
            for(int k=max(j-si[x],0);k<=min(si[y],j);k++)
            {
                ll cnt=k*(m-k)+(si[y]-k)*(n-m+k-si[y]);
                f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]+cnt*e[i]);
            }
        si[x]+=si[y];
    }
}
int main()
{
    read(n,m);
    m=min(m,n-m);
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        read(u,v,w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0);
    printf("%lld\n",f[1][m]);
    return 0;
}