bzoj 树上染色

题意：

给定一棵n个点的树，把其中k个染成黑色，定义价值为黑色节点两两之间的距离和+白色节点两两之间的距离，求最大价值

分析：

树上dp

typedef pair<LL,LL> P;
LL N,K;
const LL maxn = 2000+10;
std::vector<P> G[maxn];
LL size[maxn];
LL
dp[maxn][maxn];
LL
tmp[maxn];
void dfs(LL node,LL fa){
// fill(dp,dp+N+1,)
size[node] = 1;
for(int i = 0;i < (int)G[node].size();++i){
P p = G[node][i];
LL c = p.first;
if(c == fa) continue;
dfs(c,node);
fill(tmp,tmp+1+N,0);
// 下面的操作是n^2 的
for(LL i = 0;i <= size[node]; ++i)
for(LL j = 0;j <= size[c]; ++j)
{
if(i+j <= K)
tmp[i+j] = max(tmp[i+j],dp[node][i]+dp[c][j]+1ll*p.second*(1ll*j*(K-j) + 1ll*(size[c]-j)*(N-size[c]-(K-j))));
}
size[node] += size[c];
for(LL i = 0;i <= K; ++i)
dp[node][i] = tmp[i];
}
}
int main(void)
{
cin>>N>>K;
LL u,v,w;
for(LL i= 1;i < N; ++i){
scanf("%lld%lld%lld",&u,&v,&w);
G[u].Pb(P(v,w));
G[v].Pb(P(u,w));
}
dfs(1,-1);
cout<<dp[1][K]<<endl;
return 0;
}

最后

以上就是无语山水为你收集整理的bzoj4033[HAOI2015] 树上染色 dpbzoj 树上染色的全部内容，希望文章能够帮你解决bzoj4033[HAOI2015] 树上染色 dpbzoj 树上染色所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。