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

这道题的题解已经相当多了，但是我认为都没有对本道题做一个足够清晰的剖析，尤其是对于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$的情况即可。 下面放代码（内有注解） ```cpp #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; } ``` 以上就是本道题的题解，不知道你是否看懂了呢。如有不明白的地方，欢迎提问。