403098: GYM101005 A Tree Search

Memory Limit:16 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Tree Searchtime limit per test1 secondmemory limit per test16 megabytesinputstandard inputoutputstandard output

You are given a tree with N nodes, each node has an associated cost. You need to answer M questions of the type: "which is the maximum cost of a path that contains node Q?".

Input

The first line of the input contains two integers N and M (1 ≤ N, M ≤ 100.000). The second line contains N integers representing the cost of the nodes ( - 20.000 ≤ cost ≤ 20.000). Each of the next N - 1 line contains two integers representing an edge between two nodes. On each of the next M lines there is a single integer Q corresponding to a question.

Output

The output should contain M lines. On line i print a single integer representing answer for the i-th question.

ExampleInput
5 2
-3 4 5 6 3
1 2
1 3
2 5
2 4
1
2
Output
12
13

加入题单

上一题 下一题 算法标签: