题解 P3177 【[HAOI2015]树上染色】

2018-10-15 19:36:00


这道题的题解已经相当多了,但是我认为都没有对本道题做一个足够清晰的剖析,尤其是对于DP的部分。所以我希望我的这篇题解能够在以前各位的题解的基础上更进一步,让大家有一个更清晰的理解。

先强调一下,这道题的细节非常重要,一定要注意!


题目要求将k个点染成黑色,求黑点两两距离及白点两两距离,使他们之和最大。

我们可以将距离转化为路径,然后再将路径路径拆分成边,就可以记录每条边被经过的次数,直接计算即可。

很简单对吧?那么问题来了,距离转化为路径好理解,路径拆为边也好说,可是每条边被经过的次数怎么计算呢?

我们可以这样想,我们任意取两个同色的点,对于每一条边,若不在这两个点的路径上,我们自然不考虑,若是在两个点的路径上,那么这条边的计数加一。我们可以转换一下,若是两个点在边的一侧,则不影响计数,若在边的两侧,则边的计数加一。那么我们推广一下,便可以得出,一条边的两侧每有一对同色点,这条边就要被经过一次。也就是说,一条边被经过的次数等于边的两侧同色点个数的乘积。那么我们便可以求出每条边被经过的次数

$tot=k*(m-k)+(sz[v]-k)*(n-m-sz[v]+k)$

$m$ 表示题目要求选的黑点数, $sz[v]$ 表示当前子节点的子树大小, $k$ 表示当前子节点的子树上已选择的黑点数

有了这个结论,我们就可以轻松地得出DP方程了。

$f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+tot*e[i].w)$

就是关于这个方程让我在做题的时候纠结了好久,为什么 $k$ 正序排列就是对的,倒序排列就是错的?已有的题解也没有做出很好的解释,我A了之后也没有继续研究。多亏了帮同学找树形DP入门题时我重新注意到了这道题,使我对这一奇怪的现象产生了疑惑。得到了DDOSvoid大佬的帮助并进行了多次试验后,我终于明白了其中的原因,也让我对这道题的理解加深了数层。

这道题 $k$ 前几篇题解必须正序枚举的原因并不是什么要用 $j-k$ 更新答案,而是因为正序枚举 $k$ 是从 $0$ 开始的,而这道题的状态转移必须要先将 $k=0$ 的状态转移过来才能成立。也就是说,这只是个巧合, $j$ 的枚举要倒序没错,但 $k$ 的枚举必须正序简直就是无稽之谈。要想避免这一情况,只需提前转移一下 $k=0$ 的情况即可。

下面放代码(内有注解)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc getchar
#define maxn 2005
using namespace std;

inline ll read(){
    ll a=0;int f=0;char p=gc();
    while(!isdigit(p)){f|=p=='-';p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return f?-a:a;
}

struct ahaha{
    int w,to,next;
}e[maxn<<1];int tot,head[maxn];
inline void add(int u,int v,int w){
    e[tot].w=w,e[tot].to=v,e[tot].next=head[u];head[u]=tot++;
}

int n,m,sz[maxn];
ll f[maxn][maxn];
void dfs(int u,int fa){
    sz[u]=1;f[u][0]=f[u][1]=0;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;if(v==fa)continue;
        dfs(v,u);sz[u]+=sz[v];
        for(int j=min(m,sz[u]);j>=0;--j){   //此处倒序枚举是为了避免重复选取
            if(f[u][j]!=-1)    //在DP前应先加上当前子节点的子树纯白色的情况,这是下面也倒序枚举的前提
                f[u][j]+=f[v][0]+(ll)sz[v]*(n-m-sz[v])*e[i].w;
            for(int k=min(j,sz[v]);k;--k){
                if(f[u][j-k]==-1)continue;
                ll val=(ll)(k*(m-k)+(sz[v]-k)*(n-m-sz[v]+k))*e[i].w;   //当前情况下连接子节点的边的贡献
                f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+val);
            }
        }
    }
}

int main(){memset(head,-1,sizeof head);
    n=read();m=read();
    if(n-m<m)m=n-m;
    for(int i=1;i<n;++i){
        int u=read(),v=read(),w=read();
        add(u,v,w);add(v,u,w);
    }memset(f,-1,sizeof f);
    dfs(1,-1);
    printf("%lld",f[1][m]);
    return 0;
}

以上就是本道题的题解,不知道你是否看懂了呢。如有不明白的地方,欢迎提问。