题意：用k个机器人去遍历有n个节点的有根树，边权代表一个机器人通过这条边的代价，求最小代价。

\(k\le 10\)

背包走起

\(f_{u,i}\) 表示遍历完完 \(u\) 子树后留 \(i\) 个机器人在 \(u\) 子树内，\(v\) 是 \(u\) 的子节点，\(val_{u,v}\) 表示 \(u \leftrightarrow v\) 的边权
\[ f_{u,i}=\min(f_{v,0}+2\times val_{u,v},\min \{ f_{u,i-j}+f_{v,j}+j\times val_{u,v} \}) \]
对于 \(f_{v,0}+2\times val_{u,v}\)，很显然，派一只机器人去 \(v\) 子树逛一圈回来即 \(f_{v,0}\)，通过 \(u \leftrightarrow v\) 两次即 \(2\times val_{u,v}\)

对于后面那个柿子，枚举要留 \(j\) 个机器人在 \(v\) 子树内，那么其实就派 \(j\) 个机器人过去就完事了，通过 \(u \rightarrow v\) 共 \(j\) 次

注意枚举顺序，不要单棵子树重复计算了

答案就是 \(f_{s,k}\)

// This code writed by chtholly_micromaker(MicroMaker)#include <bits/stdc++.h>#define reg registerusing namespace std;const int MaxN=10050;struct Edge{ int nxt,to,w;}E[MaxN<<2];template <class t> inline void read(t &s){ s=0; reg int f=1; reg char c=getchar(); while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) s=(s<<3)+(s<<1)+(c^48),c=getchar(); s*=f; return;}int n,s,k;int hd[MaxN],en;int f[MaxN][15];inline void adde(int u,int v,int w){ ++en; E[en]=(Edge){hd[u],v,w}; hd[u]=en; return;}inline void checkmin(int &x,int y){ if(x>y) x=y; return;}inline void dfs(int u,int fa){ for(int i=hd[u];~i;i=E[i].nxt) { reg int v=E[i].to; if(v==fa) continue; dfs(v,u); for(int V=k;V>=0;--V) { f[u][V]+=f[v][0]+2*E[i].w; for(int j=0;j<=V;++j) checkmin(f[u][V],f[u][V-j]+f[v][j]+j*E[i].w); } } return;}inline void work(){ memset(hd,-1,sizeof hd);en=0; memset(f,0,sizeof f); reg int u,v,w; for(int i=1;i<n;++i) { read(u);read(v);read(w); adde(u,v,w); adde(v,u,w); } dfs(s,0); printf("%d\n",f[s][k]); return;}signed main(void){ while(cin>>n>>s>>k) work(); return 0;}