CF743D Chloe and pleasant prizes

慷慨的奥林匹克竞赛赞助商允许所有参赛者自行选择一份奖品。圣诞节即将到来，因此赞助商决定用他们准备的奖品来装饰圣诞树。 他们为参赛者准备了 $n$ 件奖品，并在每件奖品上写了一个唯一的编号（从 $1$ 到 $n$ 的整数）。第 $i$ 号奖品有一个整数 $a_i$，表示这份奖品的愉悦值。愉悦值可以为正、负或零。赞助商把 $1$ 号奖品挂在树顶。其余所有奖品都通过绳子系在其它某件奖品上，使得每件奖品都直接或间接挂在 $1$ 号奖品下。形式上，这些奖品形成了一棵有 $n$ 个节点的有根树。 发奖过程如下：参赛者们一个接一个来到圣诞树前，挑选一份还没有被选的奖品，并剪断该奖品所悬挂的绳子。注意，与该奖品相连且挂着其他奖品的绳子不会被剪断。因此，参赛者不仅获得所选择的奖品，还能获得所有“挂”在它下面的奖品（包括间接挂在它下面的）。 我们的朋友 Chloe 和 Vladik 并列获得了第一名，他们将同时选取奖品！为了避免争抢，他们约定选择两份不同的奖品，且要求这两份奖品对应的“挂在其下方的所有奖品集合”之间没有交集。换句话说，不存在任意一份奖品同时挂在 Chloe 选中的奖品和 Vladik 选中的奖品下方。在所有可能的选择方案中，他们会选择让他们得到的总愉悦值最大的方案。 请输出 Vladik 和 Chloe 能够获得的最大的总愉悦值。如果他们无法做到不争抢地选择奖品，输出 Impossible。

第一行包含一个整数 $n$，表示奖品的数量（$1\leq n\leq 2\cdot 10^{5}$）。 第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$（$-10^9\leq a_i\leq 10^9$），表示每份奖品的愉悦值。 接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1\leq u_i,v_i\leq n$，$u_i\neq v_i$），表示奖品 $u_i$ 和 $v_i$ 之间有一根绳子相连。奖品编号顺序可以任意；$v_i$ 可以挂在 $u_i$ 上，或者 $u_i$ 挂在 $v_i$ 上。 保证所有奖品通过一系列绳子最终都挂在 $1$ 号奖品下。

如果 Chloe 和 Vladik 能够不争抢地各选一份奖品，输出一个整数，表示他们可以获得的最大总愉悦值。 如果无法实现，输出 Impossible。

由 ChatGPT 5 翻译