【HAOI2015】樹上染色

這題思路好神仙啊，首先顯然是樹形dp，f[i][j]表示在以i為根的子樹中選j個黑點對答案的貢獻（并不是當前子樹最大值），dp時只考慮i與兒子連邊的貢獻。此時（i，son[i]）產生的收益是（設子樹大小為size[i]）子樹上的黑點個數（j）與子樹外的黑點個數（m - j）的乘積乘上這條邊的邊權（w[i]）加上子樹上白點的個數（size[i] - j）乘以子樹外白點的個數（n - m - size[i] + j）再乘以邊權，這些貢獻是在加入了根節點以后才產生的新的貢獻，與子樹上黑白點如何分配無關。

#include<iostream> #include<cstring> #include<cstdio> #define int LL #define LL long long #define ma(x) memset(x,0,sizeof(x)) #define MAXN 3010 using namespace std; struct edge {int u,v,w,nxt;#define u(x) ed[x].u#define v(x) ed[x].v#define w(x) ed[x].w#define n(x) ed[x].nxt }ed[2000000]; int first[MAXN],num_e; #define f(x) first[x] int f[MAXN][MAXN],du[MAXN],root; int n,nk,size[MAXN],tmp[MAXN]; void dfs(int x,int fa) {size[x]=1;for(int i=f(x);i;i=n(i))if(v(i)!=fa)dfs(v(i),x);for(int i=f(x);i;i=n(i))if(v(i)!=fa){ma(tmp);for(int j=0;j<=size[x]&&j<=nk;j++)for(int k=0;k<=size[v(i)]&&k+j<=nk;k++){tmp[j+k]=max(tmp[j+k],f[x][j]+f[v(i)][k]+k*(nk-k)*w(i)+(size[v(i)]-k)*(n-nk-size[v(i)]+k)*w(i));}for(int j=0;j<=nk;j++)f[x][j]=tmp[j];size[x]+=size[v(i)];} } inline void add(int u,int v,int w); signed main() { // freopen("in.txt","r",stdin); // freopen("2.in","r",stdin);scanf("%lld%lld",&n,&nk);int a,b,c;for(int i=1;i<n;i++){scanf("%lld%lld%lld",&a,&b,&c);du[a]++;du[b]++;add(a,b,c);add(b,a,c);}for(int i=1;i<=n;i++)if(du[i]==1){root=i;break;}dfs(root,0);cout<<f[root][nk]<<endl; } inline void add(int u,int v,int w) {++num_e;u(num_e)=u;v(num_e)=v;w(num_e)=w;n(num_e)=f(u);f(u)=num_e; }

?

轉載于:https://www.cnblogs.com/Al-Ca/p/11198618.html

總結

以上是生活随笔為你收集整理的【HAOI2015】树上染色的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。