P3177 [HAOI2015]树上染色
斯德哥尔摩
2018-07-30 20:11:03
[P3177 [HAOI2015]树上染色](https://www.luogu.org/problemnew/show/P3177)
这个题看到受益和最大，还是树上的，立马想到树形$DP$。
然后想到树形$DP$本蒟蒻就不会了。。。
以下抄自题解：
设$dp[u][i]$表示以$u$为根的子树中，选择$i$个黑节点，对答案有多少贡献。
为什么说“对答案有多少贡献”呢？
主要是想到一点：分别考虑每条边对答案的贡献。
即：边一侧的黑节点数*另一侧的黑节点数*边权+一侧的白节点数*另一侧的白节点数*边权。
这点很容易证明，但是不容易想到（原因是我太弱了）。
然后情况就明了了，整个问题成了一个树形背包，考虑每个子节点分配多少个黑色节点（体积），然后算出这条边对答案的贡献（价值）。
这里再一次强调“贡献”，是因为这个贡献不只是在当前子树内，而是对于整棵树来说的。
转移方程长这样：
$$dp[u][i]=max(dp[u][i],dp[u][i-j]+dp[v][j]+val)$$
其中$v$为$u$的子节点，$j$为在这个子节点中选择的黑色点的个数，$val$为这条边的贡献：
$$val=j*(k-j)*w+(size[v]-j)*(n-m+j-size[v])* w$$
其中$w$为这条边的边权，$n$为总的节点数，$m$为总的需要选择的黑色节点数，$size[v]$为以$v$为根的子树的节点数量。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 2010
using namespace std;
int n,m,c=1;
int head[MAXN],fa[MAXN],size[MAXN];
long long dp[MAXN][MAXN];
struct Tree{
int next,to,w;
}a[MAXN<<1];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline void add(int u,int v,int w){
a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
a[c].to=u;a[c].w=w;a[c].next=head[v];head[v]=c++;
}
void dfs(int rt){
size[rt]=1;
dp[rt][0]=dp[rt][1]=0;
for(int i=head[rt];i;i=a[i].next){
int will=a[i].to;
if(will!=fa[rt]){
fa[will]=rt;
dfs(will);
size[rt]+=size[will];
}
}
for(int i=head[rt];i;i=a[i].next){
int will=a[i].to;
if(will==fa[rt])continue;
for(int j=min(m,size[rt]);j>=0;j--)
for(int k=0;k<=min(size[will],j);k++)
if(dp[rt][j-k]!=-1){
long long val=(long long)(k*(m-k)+(size[will]-k)*(n-size[will]-(m-k)))*a[i].w;
dp[rt][j]=max(dp[rt][j],dp[rt][j-k]+dp[will][k]+val);
}
}
}
void work(){
dfs(1);
printf("%lld\n",dp[1][m]);
}
void init(){
int u,v,w;
n=read();m=read();
m=min(m,n-m);
for(int i=1;i<n;i++){
u=read();v=read();w=read();
add(u,v,w);
}
memset(dp,-1,sizeof(dp));
}
int main(){
init();
work();
return 0;
}
```