洛谷P3177 [HAOI2015] 树上染色 题解

题目链接：P3177 [HAOI2015] 树上染色

题意：

有一棵点数为 $n$ 的树，树边有边权。给你一个在 $0 \sim n$ 之内的正整数 $m$ ，你要在这棵树中选择 $m$ 个点，将其染成黑色，并将其他 的 $n-m$ 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。

upd.20220531 由于本人对树上背包掌握不熟，导致复杂度写假了

其实是题解区普遍写错罢了。

不过原文只是没用刷表法

于是在原文基础上做了修改，不影响观感，请放心食用（逃

---

显然树上背包

设 $dp[u][j]$ 表示 $u$ 所在子树染了 $j$ 个黑点的最大价值

容易推出一个大概的方程

$$dp[u][j]=\max(dp[u][j],dp[u][j-k]+dp[v][k]+\text{val})$$

注：下文会提到这个转移方程是有点问题的

黑点两两距离+白点两两距离

直接去算就是 $O(n^2)$ 的了

考虑更好的计算方法

一条路径会包括若干条边

因为是树所以有很多的边会被重复走过

考虑将距离计算转化为边重复经过次数

根据乘法原理，可知边 $(u,v)$ （ $u$ 为父结点）的贡献为

$$\text{val}=w(u,v)\times(k(m-k)+(\text{sz}[v]-k)(n-m-\text{sz}[v]+k))$$

upd.20220531 然后填表法写出来就是这样的（原文代码）

for(int i=head[u]; i; i=e[i].next)
{
    int v=e[i].v;
    if(v==f)continue;
    dfs(v,u);
    sz[u]+=sz[v];
    for(int j=min(sz[u],m); j>=0; j--)
    {
        if(dp[u][j]>=0) // k正着枚举的时候这个就不用了
            dp[u][j]+=dp[v][0]+sz[v]*(n-m-sz[v])*e[i].w;
        for(int k=min(sz[v],j); k>0; k--) // 这里正着枚举也可以
        {
            if(dp[u][j-k]<0)continue;
            int val=(k*(m-k)+(sz[v]-k)*(n-m-sz[v]+k))*e[i].w;
            dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]+val);
        }
    }
}

不难发现这个其实复杂度是可以被卡到 $O(nm^2)$ 的

所以考虑刷表法，即

$$dp[u][j+k]=\max(dp[u][j+k],\text{tmp}[j]+dp[v][k]+\text{val})$$

这里的 $\text{tmp}[j]$ 是上一轮的 $dp[u][j]$ ，刷表的过程中会被刷坏，所以要先存一下

这样时间复杂度才是严格的 $O(nm)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)

int n,m;
struct Edge
{
    int u,v,w,next;
}e[N<<1];
int pos=1,head[N],sz[N],tmp[N],dp[N][N];
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
void dfs(int u,int f)
{
    sz[u]=1;
    dp[u][0]=dp[u][1]=0;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==f)continue;
        dfs(v,u);
        for(int j=0; j<=min(sz[u],m); j++)
            tmp[j]=dp[u][j];
        for(int j=0; j<=min(sz[u],m); j++)
            for(int k=0; k<=sz[v]&&j+k<=m&&tmp[j]>=0; k++)
            {
                int val=(k*(m-k)+(sz[v]-k)*(n-m-sz[v]+k))*e[i].w;
                dp[u][j+k]=max(dp[u][j+k],tmp[j]+dp[v][k]+val);
            }
        sz[u]+=sz[v];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v,w; i<n; i++)
    {
        cin >> u >> v >> w;
        addEdge(u,v,w);addEdge(v,u,w);
    }
    memset(dp,0xc0,sizeof(dp));
    dfs(1,1);
    cout << dp[1][m] << endl;
    return 0;
}

这一段可以跳过，只是详细解释了link的东西，

而且ta的代码复杂度也是假的，因为都是填表法

注意到有些人 $k$ 倒序枚举，要先转移 $k=0$ 的情况，这里解释一下

关于为什么要先将 $k=0$ 的转移

观察方程，因为如果直接倒序枚举，最后一次 $k=0$ 的枚举

会出现 $dp[u][j]=\max(dp[u][j],dp[u][j]+\text{val})$ 的情况

显然此时的 $dp[u][j]$ 已经被更新过了

因此会导致答案有误（偏大）

除了 $k=0$ 的特殊情况，其他时候 $k$ 随便啥顺序枚举都是可以的