## CEOI '17 P6 - Chase

View as PDF

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 statues, numbered , and 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 there are pigeons. Jerry has 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 around this and neighbouring statues changes.

It all happens in the following order: First, Jerry arrives to the statue and meets pigeons. Then, he drops the breadcrumb. He leaves the statue. The pigeons from neighbouring statues move to statue 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 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.

#### Input

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

#### Output

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

#### Constraints

• An optimal route begins at statue 1.

#### 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

36

#### Explanation for Sample Output 1

One possible solution is the following. Jerry enters the park at the statue . There he encounters pigeons. He drops a breadcrumb. is now and . Next he runs to the statue and encounters pigeons. He drops the second breadcrumb. is now and . He exits the park. He encountered pigeons. Tom follows him over the same route but encounters pigeons. The difference is .