http://blog.csdn.net/mirrorgray/article/details/51123741 安利队长blog…
树形dp吧，状态挺显然的，dp[x][j]表示以x为根的子树中，选择了j个黑点的答案，但注意这个答案是整棵树的答案。 我们只需要对于每个儿子背包一遍，在最后更新一下dp[x][j]即可，具体可以看一眼程序。 非常重要的是，这个复杂度是n^2的，需要注意的是，如果我们要保证复杂度，for(int j=size[x];~j;j–)for(int k=size[ver[i]];~k;k–)必须要这么写，这样实际上是枚举整棵树中两两点对之间的lca，复杂度n^2就比较显然了。 差评下别的好多题解没有说复杂度也没有证明，我找了几份题解以为n^3卡了半天发现卡不掉仔细理性分析了下才发现是n^2的，get到了树形dp的正确姿势… 如果有人因为背包挂掉请注意是不是j和k都是倒着枚举的，如果因为这里挂掉请仔细想想原因（蒟蒻表示自己也因为这里wa掉了一屏…对于背包的处理不好…）最保险的做法是memcpy，但那样常数略大… From lyh
//By SiriusRen #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define int long long const int N=2017; int f[N][N],w[N*2],v[N*2],next[N*2],first[N],tot,size[N],n,k,xx,yy,zz; void add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;} void dfs(int x,int fa,int len){ size[x]=1; for(int i=first[x];~i;i=next[i]) if(v[i]!=fa){ dfs(v[i],x,w[i]); for(int j=size[x];~j;j--) for(int k=size[v[i]];~k;k--) f[x][j+k]=max(f[x][j+k],f[v[i]][k]+f[x][j]); size[x]+=size[v[i]]; } for(int i=0;i<=size[x];i++)f[x][i]+=i*(k-i)*len+(size[x]-i)*(n-size[x]-k+i)*len; } signed main(){ memset(first,-1,sizeof(first)); scanf("%lld%lld",&n,&k); for(int i=1;i<n;i++)scanf("%lld%lld%lld",&xx,&yy,&zz),add(xx,yy,zz),add(yy,xx,zz); dfs(1,-1,0); printf("%lld\n",f[1][k]); }