← 返回题目列表

Codeforces · 743/D

D. 克洛伊和令人愉快的奖品

中文机器翻译题面 查看原题

Chloe 和 Vladik 参加的奥运会的慷慨赞助商允许所有参赛者自行为他们选择奖品。圣诞节即将到来,赞助商决定用他们的奖品来装饰圣诞树。

他们为参赛者颁发了n个奖品,并在每个奖品上写下了一个唯一的id(从1到n的整数)。礼物 i 的特征是整数 ai——礼物的愉快程度。礼物的愉悦感可以是正值、负值或零。赞助商将礼物 1 放在树顶。所有其他礼物都挂在与其他礼物绑在一起的绳子上,以便每件礼物都挂在第一个礼物上,可能还有一系列绳子和其他礼物。形式上,这些礼物形成了一棵有 n 个顶点的有根树。

颁奖程序是这样的:参与者陆续来到树前,选择剩余的礼物中的任何一个,并剪断奖品所挂的绳子。请注意,用于将其他奖品挂在所选奖品上的所有绳子都不会被切断。因此,参赛者会获得所选的礼物以及挂在上面的所有礼物,可能还有一系列绳子和其他礼物。

我们的朋友Chloe和Vladik分享了奥林匹克竞赛第一名,他们将同时评选奖品!为了避免打架,他们决定选择两件不同的礼物,这样用一系列绳子挂在他们身上的礼物和另一件礼物就不会相交。换句话说,不应该有任何礼物同时挂在Chloe选择的礼物和Vladik选择的礼物上。他们将从所有可能的变体中选择这样一对奖品,使得他们在割断绳子后获得的所有礼物的愉悦感之和尽可能大。

打印 Vladik 和 Chloe 可以获得的最大愉悦度总和。如果他们不可能在不战斗的情况下选择礼物,请打印“不可能”。

输入

第一行包含一个整数 n (1 ≤ n ≤ 2·105) – 礼物的数量。

下一行包含 n 个整数 a1, a2, ..., an ( - 109 ≤ ai ≤ 109) – 礼物的愉快程度。

接下来的 (n - 1) 行每行包含两个数字。这些行的第 i 行包含整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 树边的描述。这意味着编号为 ui 和 vi 的礼物用绳子相互连接。绳索描述中的礼物 ID 可以按任意顺序给出:vi 挂在 ui 上或 ui 挂在 vi 上。

保证所有礼物都挂在第一个礼物上,可能还有一系列绳子和另一个礼物。

输出

如果 Chloe 和 Vladik 可以在不打斗的情况下选择奖品,请打印单个整数——他们可以在一起的最大可能的愉快程度。

否则打印不可能。

示例

输入 #1

8
0 5 -1 4 3 2 6 5
1 2
2 4
2 5
1 3
3 6
6 7
6 8

输出 #1

25

输入 #2

4
1 -5 1 1
1 2
1 4
2 3

输出 #2

2

输入 #3

1
-1

输出 #3

Impossible