fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int 
  5.     maxN = 1e5,
  6.     maxK = 100,
  7.     oo = 1e18;
  8. int n, k, cur;
  9. vector <int> w[maxN + 1];
  10. int vl_fst[maxN + 1],
  11.     a[2 * maxN + 1],
  12.     dp[2 * maxN + 1][maxK + 1],
  13.     p[2 * maxN + 1],
  14.     e[2 * maxN + 1];
  15. struct Limit{
  16.     int l, r;
  17. } lim[maxN + 1];
  18. int getSum(int i, int j){
  19.     return p[j] - p[i - 1];
  20. }
  21. void init(){
  22.     cin>>n>>k;
  23.     for (int i = 1; i <= n; i++)
  24.         cin>>vl_fst[i];
  25.     for (int i = 1; i < n; i++){
  26.         int u, v; cin>>u>>v;
  27.         w[u].push_back(v);
  28.         w[v].push_back(u);
  29.     }
  30. }
  31. void dfs(int u, int pre){
  32.     lim[u].l = ++cur;
  33.     for (int v: w[u])
  34.         if (pre != v)
  35.             dfs(v, u);
  36.     lim[u].r = ++cur;
  37. }
  38. void make_ea(){
  39.     dfs(1, 0);
  40.     for (int i = 1; i <= n; i++){
  41.         e[lim[i].l] = i;
  42.         e[lim[i].r] = i;
  43.         a[lim[i].l] = vl_fst[i];
  44.     }
  45.     for (int i = 1; i <= 2 * n; i++)
  46.         p[i] = p[i - 1] + a[i];
  47. }
  48. void make_dp(){
  49.     for (int i = 1; i <= 2 * n; i++)
  50.         for (int j = 1; j <= k; j++)
  51.             dp[i][j] = oo;
  52.     for (int i = 1; i <= 2 * n; i++){
  53.         int val = e[i];
  54.         if (lim[val].l == i){
  55.             for (int j = 1; j <= k; j++)
  56.                 dp[i][j] = dp[i - 1][j];
  57.             continue;
  58.         }
  59.         int l_pre = lim[e[i]].l - 1;
  60.         for (int j = 1; j <= k; j++){
  61.             int tmp,
  62.                 uv1 = dp[i - 1][j],
  63.                 uv2 = dp[l_pre][j - 1] 
  64. + getSum(lim[e[i]].l, lim[e[i]].r);
  65.             if (dp[l_pre][j - 1] == oo)
  66.                 tmp = uv1;
  67.             else tmp = min(uv1, uv2);
  68.             dp[i][j] = min(dp[i][j], tmp);
  69.         }
  70.     }
  71. }
  72. void solve(){
  73.     int org = getSum(1, 2 * n),
  74.         bu = 2e18;
  75.     for (int i = 1; i <= k; i++)
  76.         bu = min(bu, dp[2 * n][i]);
  77.     cout<<org - bu;
  78. }
  79. signed main() {
  80.     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  81.     init(); make_ea(); make_dp(); solve();
  82. }
Success #stdin #stdout 0.01s 7472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-2000000000000000000
https://ideone.com/MyfdaI
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!