T1 Median

T3 Park

source: CEOI-2017 D2T3

Original name: CHASE

Tom the cat is chasing Jerry the mouse again! Jerry is trying to gain some advantage by running into crowds of pigeons, where it is harder for Tom to follow him. Conveniently, Jerry arrived to Central Park in Ljubljana. The park has n statues, numbered 1 . . . n, and n − 1 non-intersecting passages connecting them in such a way that it is possible to reach any statue from any other statue by traversing the passages. Clustered tightly around each statue i there are p i pigeons. Jerry has v breadcrumbs in his pocket. If he drops a breadcrumb by a statue at his current location, pigeons from neighbouring statues will immediately fly to this statue to eat the breadcrumb. As a result the current number of pigeons p around this and neighbouring statues changes. It all happens in the following order: First, Jerry arrives to the statue i and meets p i pigeons. Then, he drops the breadcrumb. He leaves the statue. The pigeons from neighbouring statues move to statue i before Jerry arrives to the next statue (so they don’t count towards his count of the pigeons met). Jerry may enter the park at any statue, run down some passages (but never using the same passage twice), and then leave the park anywhere he wants. After Jerry exits the park, Tom will enter and traverse exactly the same route. By dropping at most v breadcrumbs, Jerry wants to maximize the difference between the number of pigeons Tom will meet on the route and the number of pigeons he meets. Note that only pigeons that are present at some statue right before Jerry arrives there count toward the total number of pigeons he meets. See the comment of the example for further explanation.

Input

The first line contains the number of statues n and number of breadcrumbs v. The second line contains n integers separated with a space, p 1 . . . p n . The following n−1 lines describe the passages with pairs of numbers a i and b i , which indicate there is a passage between statues a i and b i .

Output

Output only one number, maximum difference between the number of pigeons Tom meets and the number of pigeons Jerry meets.

Solution

Consider dynamic programming. Let us denote the array down[i][j] maximal difference we can made by starting at node i and continuing in one of its subtrees, dropping at most j breadcrumbs in the subtree. And let us denote the array up[i][j] maximal difference we can made by starting at one node in the subtrees of node i and end at node i, dropping at most j breadcrumbs in the subtree. When reading the edges of the tree, calculate the gain of dropping breadcrumb at each point by adding the number of pigeons of the points directly connect to node i (Do not add the number of the pigeons of the node itself!). The values of the two arrays can be computed from the i-th children and the previous value of down[][] and up[][]. The best path running through node i and its subtrees makes the difference $max^v_{j=1} up[i][j]+down[k][v-j]$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include <bits/stdc++.h>
#define For(i, l, r) for (int64_t i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int64_t i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int64_t maxn = 100010;
template <typename type>
type read() {
  type s = 0, down = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') down = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * down;
}

int64_t n, v;
int64_t gu[maxn], sumgu[maxn];
int64_t down[100001][101], up[100001][101];
struct EDGE {
  int64_t to, next;
} edge[maxn];
int64_t head[maxn], tote;
vector<int64_t> son[maxn];
int64_t dfs(int64_t id, int64_t fa, int64_t dep) {
  if (dep == 0) return gu[id];
  int64_t ans = 0;
  for (auto to : son[id]) {
    if (to == fa) continue;
    ans += dfs(to, id, dep - 1);
  }
  return ans;
}
int64_t ans = 0;
void updatedp(int64_t rt, int64_t ch, int64_t fa) {
  For(i, 1, v - 1) ans = max(ans, up[rt][i] + down[ch][v - i]);
  For(i, 1, v) {
    down[rt][i] = max(down[rt][i],
                      max(down[ch][i], down[ch][i - 1] + sumgu[rt] - gu[fa]));
    up[rt][i] =
        max(up[rt][i], max(up[ch][i], up[ch][i - 1] + sumgu[rt] - gu[ch]));
  }
}
void dfs1(int64_t id, int64_t fa) {
  For(i, 1, v) {
    up[id][i] = sumgu[id];
    down[id][i] = sumgu[id] - gu[fa];
  }
  for (auto to : son[id]) {
    if (to == fa) continue;
    dfs1(to, id);
    updatedp(id, to, fa);
  }
  reverse(son[id].begin(), son[id].end()); //the gain of the path differs 
  // if you've swapped the beginning and the end. So compute it again with the nodes reversed
  For(i, 1, v) {
    up[id][i] = sumgu[id];
    down[id][i] = sumgu[id] - gu[fa];
  }
  for (auto to : son[id]) {
    if (to == fa) continue;
    updatedp(id, to, fa);
  }
  ans = max(ans, max(down[id][v], up[id][v]));
}

int32_t main() {
  n = read<int64_t>();
  v = read<int64_t>();
  For(i, 1, n) { gu[i] = read<int64_t>(); }
  For(i, 1, n - 1) {
    int64_t from, to;
    from = read<int64_t>();
    to = read<int64_t>();
    sumgu[from] += gu[to];
    sumgu[to] += gu[from];
    son[from].push_back(to);
    son[to].push_back(from);
  }
  dfs1(1, 0);
  cout << ans << endl;
  return 0;
}