CEOI '17 P6 - Chase

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 1.8s
Memory limit: 512M

Problem type

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 \dots 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 explanation of the example for further explanation.


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 \dots 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 only one number, maximum difference between the number of pigeons Tom meets and the number of pigeons Jerry meets.


  • 1 \le n \le 10^5
  • 0 \le v \le 100
  • 0 \le p_i \le 10^9
Subtask 1 (20 points)
  • 1 \le n \le 10
Subtask 2 (20 points)
  • 1 \le n \le 1\,000
Subtask 3 (30 points)
  • An optimal route begins at statue 1.
Subtask 4 (30 points)
  • No additional constraints.

Sample Input 1

12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12

Sample Output 1


Explanation for Sample Output 1

One possible solution is the following. Jerry enters the park at the statue 6. There he encounters 5 pigeons. He drops a breadcrumb. p_6 is now 27 and p_5 = p_7 = p_8 = p_9 = 0. Next he runs to the statue 7 and encounters 0 pigeons. He drops the second breadcrumb. p_7 is now 41 and p_2 = p_4 = p_6 = p_{10} = 0. He exits the park. He encountered 5 + 0 = 5 pigeons. Tom follows him over the same route but encounters p_6 + p_7 = 0 + 41 = 41 pigeons. The difference is 41 - 5 = 36.


There are no comments at the moment.