ADASALES - Ada and Travelling Salesman


Ada the Ladybug lives in Bugladesh. It is a very specific country - there are plenty of cities, but since the goverment doesn't "waste" money, there is only one simple path between each pair of cities.

Ada is working as Traveling Salesman. She travels between cities, buying and selling products. A product has fixed price in each city (same for buy/sale). Since Ada travels with bike (to avoid payments for travels) so she can carry at most one item at a moment.

She is currently in some city, and she wants to choose such city, that she will make as much money as possible by travelling to that city (by simple path). Can you help her?

Input

The first line will contain 0 < N ≤ 105, 0 < Q ≤ 5*105, number of cities and number of queries respectively.

Then one line with N integers follow, 1 ≤ Ai ≤ 109, the price in ith city.

Afterward N-1 lines follow, each containing two numbers 0 ≤ i,j < N (i ≠ j), meaning that there is a simple path between city i and city j.

Then Q lines follows, each containing exactly one integer 0 ≤ i < N- the city in which Ada begins.

Output

Print Q lines, the maximal amount of money, Ada can earn.

Example Input

6 6
1 2 3 4 5 4
1 0
1 2
1 3
3 4
4 5
0
1
2
3
4
5

Example Output

4
3
3
1
1
2

Example Input

5 2
1 5 2 4 3
0 1
1 2
2 3
3 4
0
2

Example Output

6
3

Output explanations [Possible destination cities of first example input]

4
4
4
2
2
2

Note that some of the destinations might have ended somewhere else, but it would result in same income!


hide comments
manh2004: 2021-01-29 11:08:33

I'm a fag

Last edit: 2021-01-29 16:03:05
weathervane: 2021-01-25 00:44:05

@morass I don't get why there can be more queries than there are cities. Does it have to be a different ending city than a previous one, or just repeat the same answer? It would be clear if the examples showed such a case.

Last edit: 2021-01-25 00:47:20
an09mous: 2020-04-05 15:05:40

My first problem with DP on trees.AC in one go.

nadstratosfer: 2019-07-07 04:57:37

Statement is poorly worded, had to analyze sample cases to understand what we're asked to do.

- "simple paths" = bidirectional roads. A path between 2 cities here can consist of many such roads.
- Ada can buy/sell as many times as she wants, but she visits every city on her path exactly once.

For first case, starting from 5, she will travel via 4-3-1 to 2. She will buy an item in 5 (money = -4), sell at 4 (-4+5 = 1), buy again in 1 (1-2 = -1) and sell in 2 (-1+3 = 2).

debarun: 2019-04-01 00:02:23

@Morass does ada initially has a product to sell when she is at the starting city or she must buy a product and then sell?

Rohit Agarwal: 2018-11-15 22:14:44

@Morass: Hi! Could you please give me some hint on test-case 13? It's failing in that case. You could see my latest submission. thanks!

Edit: It was a silly mistake. I got AC. thanks! Enjoyed the problem!! :D

Last edit: 2018-11-15 22:32:54
zagymbef: 2018-10-19 08:26:14

This is the code for this problem : http://bit.ly/2M6Vb5F
^_^

Last edit: 2019-01-11 17:08:17
jmr99: 2018-10-18 07:42:15

can anybody explain it a little bit unable to understand the output what exactly we have to print.??

soham_12345: 2018-06-12 10:38:10

Hi @morass . Can you once have a look at my code? I am getting TLE but I don't know why. This is the second time I coded in out dp and got a TLE. But I am not understanding the reason. Seems O(N) to me. Can you please help

vivek_shah98: 2018-06-05 16:44:09

Can't understand what question wants us to print!! Question is unclear to me.


Added by:Morass
Date:2017-02-12
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All