树上分组背包

题意：给定一棵 n 个节点的树，树的某个节点 s 上有 k 个机器人。要分配这些机器人去遍历这颗树，求经过的边的最小权值和。

分析：对于某一棵子树，如果进去一个机器人，它要么出来，要么不出来。如果有一个机器人出来了，就不能有第二个机器人出来。因为让第一个人去走第二个人要走的路，比第二个人自己走再走出来肯定要优 (证：如果第一个人单独走，走过的每一条边只经过两遍，如果两个人走一个人走的路，既然都要进去出来，那么出口处的路会经过 4 遍，比前者差，证毕)。因此第二个人就可以不进入这棵树。所以我们可以得到一个优美而且正确而且高效率的函数：

$f(i,j)$

$f(i,j)$表示 i 节点进去不出来 j 个机器人。如果 j 等于 0 的话表示进去一个人出来。所以有 $f(i,j)=min(∑(f(k,l)+w(i,k))(∑l=j,(i,k)∈E))$, 这其实就是一个分组的背包问题，物品是子节点的 j 值，每个子节点是一组，要达到当前节点 j 值同时最小化 $f(i,j)$。于是时间复杂度为： $O(nk^2)$

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 10000

using namespace std;

int u[MX*2],v[MX*2],w[MX*2];
int fst[MX+1],nxt[MX*2],lnum,n,s,k;
int f[MX][11];

void addeg(int nu,int nv,int nw)
{
    nxt[++lnum]=fst[nu],fst[nu]=lnum,u[lnum]=nu,v[lnum]=nv,w[lnum]=nw;
}

void dfs(int node,int fat)
{
    for(int i=fst[node];i!=-1;i=nxt[i])
    {
        if(v[i]==fat)continue;
        dfs(v[i],node);
        for(int j=k;j>=0;j--)
        {
            f[node][j]+=f[v[i]][0]+w[i]*2;
            for(int l=1;l<=j;l++)f[node][j]=min(f[node][j],f[node][j-l]+f[v[i]][l]+l*w[i]);
        }
    }
}

int main()
{
    int a,b,c;
    while(cin>>n>>s>>k)
    {
        memset(fst,0xff,sizeof(fst)),memset(f,0,sizeof(f)),lnum=-1;
        for(int i=1;i<n;i++)scanf("%d%d%d",&a,&b,&c),addeg(a,b,c),addeg(b,a,c);
        dfs(s,0),printf("%d\n",f[s][k]);
    }
    return 0;
}