P3177 [HAOI2015]树上染色

考虑证明树上背包的上下界复杂度。
考虑(T_u = sum_{p_v = u}T_v + t_u)
(t_u = (1) * (siz_{v_1}) + (siz_{v_1} + 1) * siz_{v_2} ...... + siz_{v_k} * (1 + sum v_j))
考虑全部拆出来
(O(all) = sum_{p,q,P(p) == P(q)} siz_p siz_q)
考虑把(siz_p * siz_q)写作(p,q)的对数，那么显然是一个点对只会被处理一次，即在他们的LCA处。
容易写挂。

思考怎么严格枚举已经结束的子树点数量。

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long 
#define N 2005

int n,k;

struct P{
	int to,next,v;
}e[N << 1];
int cnt,head[N];

inline void add(int x,int y,int v){
	e[++cnt].to = y;
	e[cnt].next = head[x];
	e[cnt].v = v;
	head[x] = cnt;
}

int siz[N];
ll f[N][N];

inline void dfs(int u,int fa){
	siz[u] = 1;
	f[u][0] = f[u][1] = 0;	
	for(int i = head[u];i;i = e[i].next){
		int v = e[i].to;
		if(v == fa)continue;
		dfs(v,u);
		
		for(int j = std::min(siz[u]+siz[v],k);j >= 0;--j)
		for(int p = std::max(j-siz[u],0);p <= std::min(j,siz[v]);++p){
			//if(f[u][j - p] == -1)continue;
			ll val = 1ll * e[i].v * p * (k - p) + 1ll * e[i].v * (siz[v] - p) * (n - k - siz[v] + p); 
			f[u][j] = std::max(f[u][j],f[u][j - p] + f[v][p] + val);
		}siz[u] += siz[v];
	}
}



int main(){
	scanf("%d%d",&n,&k);
	std::memset(f,0xcf,sizeof(f));
	for(int i = 1;i < n;++i){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z); 
	}
	dfs(1,0);
	ll ans = 0;
	std::cout<<f[1][k]<<std::endl;
}