Problem
题意简述：给定一棵 (n) 个节点的树，遍历每条边都需要费用 (w)，现在给定 (K) 个机器人，要求用这个 (K) 个机器人遍历整棵树，使得经过的费用和最小，(n le 10000, K le 10)。
Solution
设 (f[i,j]) 表示以 (i) 为根的子树全部遍历后有 (j) 个机器人没有回来的最小花费。（因为我们发现最后机器人都不回来才会最优）
特别的，(f[i,0]) 表示机器人全部回到了 (i) 点且子树全部遍历了，我们可以发现只派一个机器人去遍历然后回来是最优的。所以 (f[i,0] = sum_{j in son_i} f[j,0] + 2*w)
对于 (f[i,j])，我们可以理解为把 (j) 个不回来的机器人分配给每一个儿子，从所有的分配情况里面找到最小的。（树形背包）
[f[i,j] = min_{v in son_i,1<kle j} { f[i,j], f[i,j-k]+f[v,k]+k*w }
]
因为必须要遍历一遍，枚举 (k) 之前先要 (f[i,j] += f[v,0])，保证 (f[i,j]) 至少遍历了子树。
显然，答案是 (f[s][K])。
Code
Talk is cheap.Show me the code.
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x=0,f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int N = 10007;
int n,rt,K,cnt;
int head[N];
int f[N][11];
struct Edge {
int next,to,w;
}edge[N<<1];
inline void add(int u,int v,int w) {
edge[++cnt] = (Edge)<%head[u],v,w%>;
head[u] = cnt;
}
void Dfs1(int u,int fa) {
for(int i=head[u];i;i=edge[i].next) {
int v = edge[i].to, w = edge[i].w;
if(v == fa) continue;
Dfs1(v,u);
for(int j=K;j>=1;--j) {
f[u][j] += f[v][0] + 2*w;
for(int k=1;k<=j;++k)
f[u][j] = min(f[u][j], f[u][j-k]+f[v][k]+k*w);
}
f[u][0] += f[v][0] + 2*w;
}
}
void work() {
cnt = 0;
memset(f, 0, sizeof(f));
memset(head, 0, sizeof(head));
rt = read(), K = read();
for(int i=1,u,v,w;i<n;++i) {
u = read(), v = read(), w = read();
add(u,v,w), add(v,u,w);
}
Dfs1(rt,0);
printf("%d
",f[rt][K]);
}
int main()
{
while(~scanf("%d",&n))
work();
return 0;
}
/*
3 1 1
1 2 1
1 3 1
3 1 2
1 2 1
1 3 1
3
2
*/
Summary
基础树形背包题。