ACdream 1032 Component

Component

Time Limit: 5000ms

Memory Limit: 64000KB

This problem will be judged on ACdream. Original ID: 1032
64-bit integer IO format: %lld Java class name: (No Java Yet)

Given a tree with weight assigned to nodes, find out minimum total weight connected component with fixed number of node.

Input

The first line contains a single integer n.

The second line contains n integers $w_1,w_2,…,w_n. w_i$ denotes the weight of the node i.

The following (n−1) lines with two integers ai and bi, which denote the edge between ai and bi.

Note that the nodes are labled by $1,2,…,n.$

$(1\leq n\leq 2⋅10^3,1\leq w_i\leq 10^5)$

Output

$n$ integers $c_1,c_2,…,c_n. c_i$ stands for the minimum total weight component with i nodes.

Sample Input

Sample Output

1 3 6

Source

ftiasch

解题：树形dp

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 vector<int>g[maxn];

 int val[maxn],dp[maxn][maxn],n,son[maxn],ans[maxn];

 void dfs(int u,int fa){

     dp[u][] = val[u];

     dp[u][] = ;

     son[u] = ;

     for(int i = g[u].size()-; i >= ; --i){

         if(g[u][i] == fa) continue;

         dfs(g[u][i],u);

         son[u] += son[g[u][i]];

         for(int j = son[u]; j > ; --j){

             for(int k = ; k <= j; ++k)

                 dp[u][j] = min(dp[u][j],dp[g[u][i]][j - k] + dp[u][k]);

         }

     }

     for(int i = son[u]; i >= ; --i)

         ans[i] = min(ans[i],dp[u][i]);

 }

 int main(){

     while(~scanf("%d",&n)){

         for(int i = ; i < maxn; ++i) g[i].clear();

         for(int i = ; i <= n; ++i) scanf("%d",val + i);

         memset(dp,0x3f,sizeof dp);

         memset(ans,0x3f,sizeof ans);

         for(int i = ,u,v; i < n; ++i){

             scanf("%d%d",&u,&v);

             g[u].push_back(v);

             g[v].push_back(u);

         }

         dfs(,-);

         for(int i = ; i <= n; ++i)

             printf("%d%c",ans[i],i == n?'\n':' ');

     }

     return ;

 }

巴特西