davidwang's Blog

这是一类非线性的树形DP问题，首先我们想到F[i][s][j]表示以i为根的子树考虑了S中的儿子有j个黑点的答案

然后我们发现DP起来很有问题因为我们要考虑每一个子树的情况

首先利用背包的性质来进行DP 这样可以少去Sz这一为状态，空间就没有问题了

然后我们发现复杂度是这么一个东西

$$  Sum_x(size[x] * Sum_{y|y是x排在前面的兄弟}size[y])  $$

然后这个东西的复杂度是 $$ O(n^2) $$ 的具体证明不会 但是感受一下二叉树，菊花树,  链什么的都没什么问题

所以就这样了

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <ctime>
using namespace std;
#define LL long long
#define LD long double
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch>'9' || ch<'0';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 2010;
int to[N<<1],next[N<<1],len[N<<1],start[N],cnt,fa[N];
int q[N],size[N],k,n;
inline void connect(int x,int y,int z){
	to[++cnt]=y; next[cnt]=start[x];
	start[x]=cnt; len[cnt]=z;
}
LL f[N][N];
inline LL calc(int x,int i,int y,int j){
	return j * (k - j) + (size[y] - j) * (n - k - (size[y] - j));
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read(); k=read();
	for (int i=1;i<n;i++){
		int x=read(),y=read(),z=read();
		connect(x,y,z);
		connect(y,x,z);
	}
	int head=0,tail=1,u,v;
	q[1]=1;
	memset(fa,-1,sizeof(fa));
	fa[1]=0;
	while (head<tail){
		u=q[++head];
		for (int p=start[u];p;p=next[p]){
			v=to[p];
			if (fa[v]==-1){
				q[++tail]=v;
				fa[v]=u;
			}
		}
	}
	for (int ii=n;ii;ii--){
		int x=q[ii];
		size[x]++;
		f[x][0]=f[x][1]=0;
		for (int p=start[x];p;p=next[p]){
			if (to[p]==fa[x]) continue;
			int y=to[p];
			for (int i=min(k,size[x]);i>=0;i--)
				for (int j=min(size[y],k-i);j>=0;j--)
					f[x][i+j]=max(f[x][i+j],f[x][i]+f[y][j]+calc(x,i,y,j)*len[p]);
			size[x]+=size[y];
		}
	}
	printf("%lld\n",f[1][k]);
}