正題

題目鏈接:https://www.luogu.com.cn/problem/P3177

---

題目大意

$n$個(gè)點(diǎn)的一棵樹，將$k$個(gè)點(diǎn)染成黑色，其他是白色，使得黑點(diǎn)之間和白點(diǎn)之間兩兩距離和最大。

---

解題思路

也是統(tǒng)計(jì)每條邊的貢獻(xiàn)，設(shè)$f_{x,i}$表示節(jié)點(diǎn)$x$的子樹中有$i$個(gè)黑點(diǎn)時(shí)的最大子樹貢獻(xiàn)和。

發(fā)現(xiàn)這樣轉(zhuǎn)移是$O(n{k}^2)$的，只要限制$i$的枚舉范圍在$si{z}_x$以內(nèi)就變成$O(n^2)$了，原因是節(jié)點(diǎn)之間兩兩做了一次貢獻(xiàn)。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2100; struct node{ll to,next,w; }a[N*2]; ll n,K,tot,ls[N],f[N][N],g[N],siz[N]; void addl(ll x,ll y,ll w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;return; } void dp(ll x,ll fa){siz[x]=1;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;dp(y,x);for(ll j=0;j<=siz[x];j++)g[j]=f[x][j],f[x][j]=0;for(ll j=0;j<=siz[x];j++)for(ll k=0;k<=siz[y];k++)f[x][j+k]=max(f[x][j+k],g[j]+f[y][k]+a[i].w*(k*(K-k)+(siz[y]-k)*(n-K-siz[y]+k))); siz[x]+=siz[y];}return; } int main() {scanf("%lld%lld",&n,&K);for(ll i=1;i<n;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);addl(x,y,w);addl(y,x,w);}dp(1,1);printf("%lld",f[1][K]); }

總結(jié)

以上是生活随笔為你收集整理的P3177-[HAOI2015]树上染色【树形dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。