Description：

给出一棵 $n$ 个节点的树，边有边权，现要求你将这 $n$ 个点划分到 $m$ 个集合，集合不许为空。另要求 $1$ 号集合必须包含 $1$ 号点，并且 $1$ 号集合的大小必须正好为 $k$ 。如果一条边连接的两个点属于同一个集合，则这条边的边权将被计入总代价，问总代价最少为多少。

$1\leqslant n\leqslant 300$

Solution：

先判无解： $s+m-1>n$ 。

当 $m=2$ 时，只要一条边两个端点在同一集合中，就会产生贡献。

当 $m>2$ 时，发现我们一定尽量不会让一条边的两端都是一个非 $1$ ，因为如果我们尽量让一条边两端都不同的话，既可以减少代价，又可以尽量使得每个集合不为空，而 $m>2$ 的时候一定可以满足为每条边选出两个不同的端点，所以问题等价于给一棵树，选 $k$ 个点，最小化两个端点都被选中的边权和。

于是设 $f[i][j][0/1]$ 表示对于子树 $i$ ，选出了 $j$ 个点，根节点是否被选中的总代价，然后做一个树形背包就好了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,s;

#define MAXN 310

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

	return;

}

int f[MAXN][MAXN][2];

int g[MAXN][2];

bool v[MAXN];

void dp(int k)

{

	v[k] = true;

	memset(f[k],0x3f,sizeof(f[k]));

	f[k][0][0] = 0;f[k][1][1] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp(e[i].to);

		memset(g,0x3f,sizeof(g));

		for(int j = 0;j <= s;++j)

		{

			for(int l = 0;l <= j;++l)

			{

				g[j][0] = min(g[j][0],f[k][l][0] + min(f[e[i].to][j - l][0] + (m == 2 ? e[i].v : 0),f[e[i].to][j - l][1]));

			}

		}

		for(int j = 1;j <= s;++j)

		{

			for(int l = 1;l <= j;++l)

			{

				g[j][1] = min(g[j][1],f[k][l][1] + min(f[e[i].to][j - l][0],f[e[i].to][j - l][1] + e[i].v));

			}

		}

		memcpy(f[k],g,sizeof(g));

	}

	return;

}

int main()

{

	scanf("%d%d%d",&n,&m,&s);

	if(s + m - 1 > n)

	{

		puts("-1");

		return 0;

	}

	int a,b,c;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	dp(1);

	if(f[1][s][1] != 0x3f3f3f3f)cout << f[1][s][1] << endl;

	else puts("-1");

	return 0;

}