SP30760 ADASALES - Ada and Travelling Salesman

Ada the Ladybug 生活在一个名为 Bugladesh 的国家。这个国家的特殊之处在于，虽然城市众多，但任意两个城市之间只有一条简单的路径相连，因为政府不愿在这上面投入资金。 Ada 是一名旅行推销员，她在各个城市之间来回奔波，进行商品的买卖。在每个城市，商品都有固定价格（买入价和卖出价相同）。因为骑自行车旅行，Ada 每次只能携带一件商品。 现在，她正处于某个城市，想要选择一个可以通过简单路径到达的城市，以便获得最大的利润。你能帮助她做出选择吗？

第一行输入两个正整数 **N** 和 **Q**，分别表示城市数量和查询次数。 接下来的一行包含 **N** 个整数，第 **i** 个整数代表第 **i** 个城市的商品价格，范围是 **1 ≤ P_i ≤ 10^9**。 接着有 **N-1** 行，每行包括两个整数 **0 ≤ u, v < N** 且 **u ≠ v**，表示在城市 **u** 和城市 **v** 之间存在一条简单路径。 最后是 **Q** 行，每行包含一个整数 **0 ≤ S < N**，表示 Ada 开始所在的城市。

对于每个查询，输出一个整数，表示 Ada 能够获得的最大利润。共输出 **Q** 行，每行对应一个查询结果。

- **1 ≤ N, Q ≤ 200,000** - **1 ≤ P_i ≤ 10^9** **本翻译由 AI 自动生成**