很棒的一个树形DP。学的太渣了。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 int dp[10001][11]; 8 struct node 9 {10     int u,v,w,next;11 }edge[30001];12 int first[10001],t,flag[10001];13 int n,m;14 void CL()15 {16     t = 0;17     memset(first,-1,sizeof(first));18     memset(flag,0,sizeof(flag));19 }20 void add(int u,int v,int w)21 {22     edge[t].u = u;23     edge[t].v = v;24     edge[t].w = w;25     edge[t].next = first[u];26     first[u] = t ++;27 }28 void dfs(int u)29 {30     int i,v,j,k;31     flag[u] = 1;32     for(i = first[u];i != -1;i = edge[i].next)33     {34         v = edge[i].v;35         if(flag[v]) continue;36         dfs(v);37         for(j = m;j >= 0;j --)38         {39             dp[u][j] += dp[v][0] + 2*edge[i].w;40             for(k = 1;k <= j;k ++)41             {42                 dp[u][j] = min(dp[u][j],dp[u][j-k] + dp[v][k] + k*edge[i].w);43             }44         }45     }46 }47 int main()48 {49     int s,u,v,w,i;50     while(scanf("%d%d%d",&n,&s,&m)!=EOF)51     {52         CL();53         memset(dp,0,sizeof(dp));54         for(i = 1;i < n;i ++)55         {56             scanf("%d%d%d",&u,&v,&w);57             add(u,v,w);58             add(v,u,w);59         }60         dfs(s);61         printf("%d\n",dp[s][m]);62     }63     return 0;64 }