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 ≤ 10^{5}, 0 < Q ≤ 5*10^{5}, number of cities and number of queries respectively.
Then one line with N integers follow, 1 ≤ A_{i} ≤ 10^{9}, the price in i^{th} city.
Afterward N1 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
debarun:
20190401 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:
20181115 22:14:44
@Morass: Hi! Could you please give me some hint on testcase 13? It's failing in that case. You could see my latest submission. thanks!


zagymbef:
20181019 08:26:14
This is the code for this problem : http://bit.ly/2M6Vb5F


jmr99:
20181018 07:42:15
can anybody explain it a little bit unable to understand the output what exactly we have to print.?? 

soham_12345:
20180612 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:
20180605 16:44:09
Can't understand what question wants us to print!! Question is unclear to me. 

totallynotan:
20180413 05:20:59
:( O(N) Can't pass using java rip. I hope SPOJ has ways to accomodate languages apart from C++. I'm pretty sure this bound is pretty lenient for C++


codexter:
20180301 07:09:09
Cant understand the question. Can you provide more details for explanation of example. What are the constraints?


bottorezhan:
20180215 07:00:28
to easy for rtz 

Ashish Khurange:
20171119 09:13:09
Last edit: 20171119 09:38:56 
Added by:  Morass 
Date:  20170212 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 