D. Chloe and pleasant prizes

Codeforces

IDCF743D

Time2000ms

Memory256MB

Difficulty—

dfs and similardpgraphstrees

English · Original

Chinese · Translation

Formal · Original

Generous sponsors of the olympiad in which Chloe and Vladik took part allowed all the participants to choose a prize for them on their own. Christmas is coming, so sponsors decided to decorate the Christmas tree with their prizes. They took _n_ prizes for the contestants and wrote on each of them a unique id (integer from 1 to _n_). A gift _i_ is characterized by integer _a__i_ — pleasantness of the gift. The pleasantness of the gift can be positive, negative or zero. Sponsors placed the gift 1 on the top of the tree. All the other gifts hung on a rope tied to some other gift so that each gift hung on the first gift, possibly with a sequence of ropes and another gifts. Formally, the gifts formed a rooted tree with _n_ vertices. The prize-giving procedure goes in the following way: the participants come to the tree one after another, choose any of the remaining gifts and cut the rope this prize hang on. Note that all the ropes which were used to hang other prizes on the chosen one are not cut. So the contestant gets the chosen gift as well as the all the gifts that hang on it, possibly with a sequence of ropes and another gifts. Our friends, Chloe and Vladik, shared the first place on the olympiad and they will choose prizes at the same time! To keep themselves from fighting, they decided to choose two different gifts so that the sets of the gifts that hang on them with a sequence of ropes and another gifts don't intersect. In other words, there shouldn't be any gift that hang both on the gift chosen by Chloe and on the gift chosen by Vladik. From all of the possible variants they will choose such pair of prizes that the sum of pleasantness of all the gifts that they will take after cutting the ropes is as large as possible. Print the maximum sum of pleasantness that Vladik and Chloe can get. If it is impossible for them to choose the gifts without fighting, print _Impossible_. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 2·105) — the number of gifts. The next line contains _n_ integers _a_1, _a_2, ..., _a__n_ ( - 109 ≤ _a__i_ ≤ 109) — the pleasantness of the gifts. The next (_n_ - 1) lines contain two numbers each. The _i_\-th of these lines contains integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, _u__i_ ≠ _v__i_) — the description of the tree's edges. It means that gifts with numbers _u__i_ and _v__i_ are connected to each other with a rope. The gifts' ids in the description of the ropes can be given in arbirtary order: _v__i_ hangs on _u__i_ or _u__i_ hangs on _v__i_. It is guaranteed that all the gifts hang on the first gift, possibly with a sequence of ropes and another gifts. ## Output If it is possible for Chloe and Vladik to choose prizes without fighting, print single integer — the maximum possible sum of pleasantness they can get together. Otherwise print _Impossible_. [samples]

Chloe 和 Vladik 参加的竞赛的慷慨赞助商允许所有参赛者自行选择奖品。圣诞节即将到来，因此赞助商决定用这些奖品装饰圣诞树。他们为参赛者准备了 #cf_span[n] 个奖品，并在每个奖品上写了一个唯一的 ID（从 #cf_span[1] 到 #cf_span[n] 的整数）。奖品 #cf_span[i] 的特征是整数 #cf_span[ai] —— 奖品的愉悦值。愉悦值可以是正数、负数或零。赞助商将奖品 #cf_span[1] 放在树的顶部。其余所有奖品都悬挂在系在其他奖品上的绳子上，使得每个奖品都挂在奖品 #cf_span[1] 上，可能通过一系列绳子和其它奖品。形式上，这些奖品构成了一个具有 #cf_span[n] 个顶点的有根树。发奖流程如下：参赛者依次来到树前，选择任意一个剩余的奖品并剪断该奖品所悬挂的绳子。注意，连接在所选奖品上的其他奖品所用的绳子不会被剪断。因此，参赛者将获得所选奖品以及所有悬挂在它下面的奖品（可能通过一系列绳子和其它奖品）。我们的朋友 Chloe 和 Vladik 在竞赛中并列第一，他们将同时选择奖品！为了避免争吵，他们决定选择两个不同的奖品，使得它们各自下方通过绳子连接的所有奖品集合互不相交。换句话说，不存在任何一个奖品同时悬挂在 Chloe 选择的奖品和 Vladik 选择的奖品之下。在所有可能的方案中，他们会选择一对奖品，使得他们剪断绳子后获得的所有奖品的愉悦值之和最大。请输出 Chloe 和 Vladik 能获得的最大愉悦值之和。如果他们无法在不争吵的情况下选择奖品，请输出 _Impossible_。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]）——奖品的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 109 ≤ ai ≤ 109]）——每个奖品的愉悦值。接下来的 #cf_span[(n - 1)] 行每行包含两个数字。第 #cf_span[i] 行包含整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]，#cf_span[ui ≠ vi]）——描述树的边。这意味着编号为 #cf_span[ui] 和 #cf_span[vi] 的奖品通过一根绳子相连。绳子描述中的奖品 ID 顺序可以任意：#cf_span[vi] 悬挂在 #cf_span[ui] 上，或者 #cf_span[ui] 悬挂在 #cf_span[vi] 上。保证所有奖品都挂在奖品 #cf_span[1] 上，可能通过一系列绳子和其它奖品。如果 Chloe 和 Vladik 可以在不争吵的情况下选择奖品，请输出一个整数——他们能获得的最大愉悦值之和。否则输出 _Impossible_。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]）——奖品的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 109 ≤ ai ≤ 109]）——每个奖品的愉悦值。接下来的 #cf_span[(n - 1)] 行每行包含两个数字。第 #cf_span[i] 行包含整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]，#cf_span[ui ≠ vi]）——描述树的边。这意味着编号为 #cf_span[ui] 和 #cf_span[vi] 的奖品通过一根绳子相连。绳子描述中的奖品 ID 顺序可以任意：#cf_span[vi] 悬挂在 #cf_span[ui] 上，或者 #cf_span[ui] 悬挂在 #cf_span[vi] 上。保证所有奖品都挂在奖品 #cf_span[1] 上，可能通过一系列绳子和其它奖品。 ## Output 如果 Chloe 和 Vladik 可以在不争吵的情况下选择奖品，请输出一个整数——他们能获得的最大愉悦值之和。否则输出 _Impossible_。 [samples]

Let $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \{1, 2, \dots, n\} $, and vertex $ 1 $ is the root. Each vertex $ i \in V $ has a weight $ a_i \in \mathbb{Z} $, representing the pleasantness of the gift. Define for each vertex $ u \in V $, the **subtree sum** $ s(u) $ as the sum of weights of all vertices in the subtree rooted at $ u $, including $ u $ itself. We are to find two distinct vertices $ u, v \in V $, $ u \ne v $, such that the subtrees rooted at $ u $ and $ v $ are **disjoint** (i.e., neither is an ancestor of the other), and maximize: $$ s(u) + s(v) $$ If no such pair $ (u, v) $ exists, output "Impossible". --- **Constraints:** - $ 1 \leq n \leq 2 \cdot 10^5 $ - $ -10^9 \leq a_i \leq 10^9 $ --- **Objective:** Maximize $ s(u) + s(v) $ over all unordered pairs $ \{u, v\} $ such that $ u \ne v $ and $ u $ is not an ancestor of $ v $ and $ v $ is not an ancestor of $ u $. If no such pair exists, output "Impossible".

Samples

Input #1

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

Output #1

Input #2

Output #2

Input #3

1
-1

Output #3

Impossible

API Response (JSON)

{
  "problem": {
    "name": "D. Chloe and pleasant prizes",
    "description": {
      "content": "Generous sponsors of the olympiad in which Chloe and Vladik took part allowed all the participants to choose a prize for them on their own. Christmas is coming, so sponsors decided to decorate the Chr",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF743D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Generous sponsors of the olympiad in which Chloe and Vladik took part allowed all the participants to choose a prize for them on their own. Christmas is coming, so sponsors decided to decorate the Chr...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Chloe 和 Vladik 参加的竞赛的慷慨赞助商允许所有参赛者自行选择奖品。圣诞节即将到来，因此赞助商决定用这些奖品装饰圣诞树。\n\n他们为参赛者准备了 #cf_span[n] 个奖品，并在每个奖品上写了一个唯一的 ID（从 #cf_span[1] 到 #cf_span[n] 的整数）。奖品 #cf_span[i] 的特征是整数 #cf_span[ai] —— 奖品的愉悦值。愉悦值可以是正数、负...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \\{1, 2, \\dots, n\\} $, and vertex $ 1 $ is the root. Each vertex $ i \\in V $ has a weight $ a_i \\in \\mathbb{Z} $, representing the p...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments