{"problem":{"name":"A. Tree Search","description":{"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?\". The first line of the inp","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":16384},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10100A"},"statements":[{"statement_type":"Markdown","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## Input\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\n## Output\n\nThe output should contain M lines. On line i print a single integer representing answer for the i-th question.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10100A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}