{"raw_statement":[{"iden":"statement","content":"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?\".\n\nThe 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.\n\nThe output should contain M lines. On line i print a single integer representing answer for the i-th question.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"The output should contain M lines. On line i print a single integer representing answer for the i-th question."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ denote the number of nodes and queries, respectively.  \nLet $ G = (V, E) $ be a tree with $ |V| = N $, $ |E| = N-1 $.  \nLet $ c : V \\to \\mathbb{Z} $ be a cost function on nodes, with $ -20{,}000 \\leq c(v) \\leq 20{,}000 $.  \nLet $ Q_1, \\dots, Q_M \\in V $ be the query nodes.\n\n**Constraints**  \n1. $ 1 \\leq N, M \\leq 100{,}000 $  \n2. For all $ v \\in V $, $ c(v) \\in [-20{,}000, 20{,}000] $  \n3. $ G $ is a connected acyclic undirected graph.\n\n**Objective**  \nFor each query $ Q_i $, compute:  \n$$\n\\max_{\\substack{P \\subseteq V \\\\ P \\text{ is a path in } G \\\\ Q_i \\in P}} \\sum_{v \\in P} c(v)\n$$","simple_statement":"Given a tree with N nodes, each having a cost, answer M queries: for each query Q, find the maximum cost of any path that includes node Q.","has_page_source":false}