题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4003

题意： 

给一棵n个节点的树, 节点编号为1~n, 每条边都有一个花费值. 

有k个机器人从S点出发, 问让机器人遍历所有边,最少花费值多少?

思路：

用f(i, j)表示子树i用j个机器人的最少花费

如果从根节点出发,遍历所有节点之后再回到原点, 那么最少的花费一定是所有边的权值之和sum的两倍, 因为每条边都走了两次.

    而这题, 遍历完之后,并不需要走回出发点, 所以, 有些边只走了一次就可以了,
    如果用1台机器人走, 最少的的花费 = sum * 2 - {根节点到叶子节点路径的最大权值和}
    如果是j台机器走, 我们要让j台机器人只走一次的边的权值之和尽量大, 也就是减少的花费尽量大.

    那么, 我的状态表示为:
    f(i, j) 表示子树i用j个机器人最多可以减少的花费.
    
    对于i节点, 它的每个子节点的子树是一组物品, 我们可以选择派1,2,...j个机器人走去
    需要注意, 如果派x个机器人走向某个子节点v, 那么边edge(i, v)就会被走了x次, 花费了x*w(i, v).
    而原始的sum中每条边只走了两次, 所以走edge(i, v)的花费减少了 2*w(i,v) - x*w(i,v)

    最后可以得到状态转移式:

    f(i, j) = max{ max{f(i, j-k) + f(v, k) + 2*w(i,v) - k*w(i,v) | 1<=k<=j }  | v是i的儿子节点 }

#include <iostream>#include <algorithm>#include <string>#include <string.h>#include <vector>#include <map>#include <stack>#include <set>#include <queue>#include <math.h>#include <cstdio>#include <iomanip>#include <time.h>#include <bitset>#include <cmath>#define LL long long#define INF 0x3f3f3f3f#define ls nod<<1#define rs (nod<<1)+1const double eps = 1e-10;const int maxn = 1e4 + 10;const LL mod = 1e9 + 7;int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;}using namespace std;struct edge { int v,w,nxt;}e[maxn<<1];int head[maxn];int cnt;int f[maxn][15];int n,m,k;inline void add_edge(int u,int v,int w) { e[++cnt].v = v; e[cnt].w = w; e[cnt].nxt = head[u]; head[u] = cnt;}inline void dfs(int x,int fa) { for (int i = head[x];~i;i = e[i].nxt) { int v = e[i].v; if (v == fa) continue; dfs(v,x); for (int j = k;j >= 1;j--) { for (int l = 1;l <= j;l++) { f[x][j] = max(f[x][j],f[x][j-l]+f[v][l]+2*e[i].w-l*e[i].w); } } }}int main() { ios::sync_with_stdio(false); while (cin >> n >> m >> k) { cnt = 0; memset(head,-1, sizeof(head)); memset(f,0, sizeof(f)); int sum = 0; for (int i = 1;i < n;i++) { int u,v,w; cin >> u >> v >> w; sum += w; add_edge(u,v,w); add_edge(v,u,w); } dfs(m,0); cout << 2*sum - f[m][k] << endl; } return 0;}