bzoj4033 [HAOI2015]樹上染色

題目：https://www.lydsy.com/JudgeOnline/problem.php?id=4033

重要的思路：與其考慮每一個點對的貢獻，不如考慮每條邊的貢獻（==被經過了幾次）！

樹形dp。

總共的黑點和白點的個數都是已知的，所以知道子樹里有多少個黑點，就能算出子樹的根到它的父親的那條邊被經過多少次。

　　（因為子樹中黑點數是包含根的，所以求子樹向外的那條邊比較方便）

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=2005;
int n,k,head[N],xnt,rt,siz[N];
ll dp[N][N],ed[N];
struct Edge{int next,to;ll w;Edge(int n=0,int t=0,ll c=0):next(n),to(t),w(c) {}
}edge[N<<1];
void add(int a,int b,ll c)
{edge[++xnt]=Edge(head[a],b,c);head[a]=xnt;edge[++xnt]=Edge(head[b],a,c);head[b]=xnt;
}
void dfs(int cr,int fa)
{siz[cr]=1;for(int i=head[cr],v;i;i=edge[i].next){if((v=edge[i].to)==fa)continue;ed[v]=edge[i].w;dfs(v,cr);for(int j=min(k,siz[cr]+siz[v]);j>=0;j--)for(int l=max(0,j-siz[cr]);l<=j&&l<=siz[v];l++)dp[cr][j]=max(dp[cr][j],dp[cr][j-l]+dp[v][l]);siz[cr]+=siz[v];}if(!fa)return;for(int j=0;j<=k&&j<=siz[cr];j++)dp[cr][j]+=(j*(k-j)+(siz[cr]-j)*(n-k-(siz[cr]-j)))*ed[cr];
}
int main()
{scanf("%d%d",&n,&k);int x,y;ll z;for(int i=1;i<n;i++)scanf("%d%d%lld",&x,&y,&z),add(x,y,z);dfs(1,0);printf("%lld",dp[1][k]);return 0;
}

?