[NOI2002] 贪吃的九头蛇

考虑任意一种划给大头的方案，两端的都给了大头(bel=1)的边产生难受值，剩下n-k个果子分给m-1个头，当m-1=1时，两端都给了这个小头也产生难受值；而m-1>1的情况要好看的多，贪心的，因为未划分的果子构成一个森林，重新计算这些果子在所在树中的深度，把果子按深度排序，前m-1个个分别划分，剩下的节点任意分配，只需要保证与父亲不同即可，显然按这种分配方法能做到“零难受”。

换而言之，当m=2时只有两端分配不同才不会有难受值(废话！)；否则，只有两端都分配给了1(大头)才会有难受值。然后就能写dp了，设f[x,0/1]表示x子树中，x是否划分给了1的最小难受值之和。

\[ f[x,0]=\begin{cases} +\infty &x\text{是最大值点}\\ \sum_{x\to y} \min(f[y,0]+len_{x\to y},f[y,1]) &m=2\\ \sum_{x\to y} \min(f[y,0],f[y,1]) &m>1 \end{cases}\\ f[x,1]=\sum_{x\to y} \min(f[y,0],f[y,1]+len_{x\to y}) \]

似乎很可信的样子……可行个喘喘，怎么着也得加一位表示子树内已经分配给1的节点总数吧……反正不再列式子了（光速逃

#include <bits/stdc++.h>
using namespace std;
const int n=310;

int n,m,k;
int head[n],to[n<<1],len[n<<1],lst[n<<1];
int siz[n],f[n][n][2],tmp[n][2];

void ins(int x,int y,int w) {
    static int cnt=0;
    to[++cnt]=y,len[cnt]=w,lst[cnt]=head[x],head[x]=cnt;
    to[++cnt]=x,len[cnt]=w,lst[cnt]=head[y],head[y]=cnt;
}
void dfs(int x,int pa) {
    siz[x]=1;
    memset(f[x],0x3f,sizeof f[x]);
    f[x][0][0]=f[x][1][1]=0;
    for(int i=head[x]; i; i=lst[i]) if(to[i]!=pa) {
        int y=to[i];
        dfs(y,x); siz[x]+=siz[y];
        memcpy(tmp,f[x],sizeof f[x]);
        memset(f[x],0x3f,sizeof f[x]);
        for(int s=0; s<=k&&s<=siz[x]; ++s) 
        for(int t=0; t<=s&&t<=siz[y]; ++t) {
            f[x][s][0]=min(f[x][s][0],min(f[y][t][0]+(m==2)*len[i],f[y][t][1])+tmp[s-t][0]);
            f[x][s][1]=min(f[x][s][1],min(f[y][t][0],f[y][t][1]+len[i])+tmp[s-t][1]);
        }
    }
}

int main() {
    scanf("%d%d%d",&n,&m,&k);
    for(int x,y,w,i=n; --i; ) {
        scanf("%d%d%d",&x,&y,&w);
        ins(x,y,w);
    }
    if(m-1+k>n) {
        puts("-1");
        return 0;
    }
    dfs(1,0);
    printf("%d\n",f[1][k][1]);
    return 0;
}