問題一覧 > 通常問題

No.3660 LIS on Tree

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 73
作問者 : くらげ / テスター : sepa38 dyktr_06 t5ugu yuusaan
お気に入りにしたユーザー ProblemId : 13176 / 自分の提出
問題文最終更新日: 2026-08-30 00:04:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
MMA Contest 022 (順位表) の他の問題:

Problem Statement

There is a tree with $N$ vertices, and a non-negative integer $S_i$ is written on vertex $i$ $(1 \le i \le N)$. Edge $j$ $(1 \le j \le N-1)$ connects vertices $a_j, b_j$.

Consider choosing $1$ vertex of this tree and, starting from the chosen vertex, acting according to the following rules. Here, let $x$ be the vertex you are currently at.

  • If among the vertices adjacent to vertex $x$ there are vertices that have not been visited yet and whose written integer is greater than $S_x$, choose $1$ of those vertices and move to it.
  • If there is no such vertex, finish acting.

Find the maximum possible value of the sum of the integers written on the vertices passed through (including the start and end vertices) at the time you finish acting.

Constraints

  • $ 1 \le N \le 2 \times 10^5$
  • $ 0 \le S_i \le 10^9 (1 \le i \le N)$
  • $ 1 \le a_j, b_j \le N (1 \le j \le N-1)$
  • The given graph is a tree
  • All inputs are integers

Input

$N$
$S_1$ $S_2$ $\dots$ $S_N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$

Output

Output the answer on $1$ line.

Sample

Sample 1
Input
6
3 1 4 1 5 2
1 2
1 6
2 3
2 4
4 5
Output
6

If you first choose vertex $4$ and move in the order of vertices $4$, $5$, the sum of the integers written on the vertices passed through is $1+5=6$, and this is the maximum.

Sample 2
Input
6
2 5 8 7 0 1
1 2
2 3
2 4
2 5
2 6
Output
15
Sample 3
Input
15
999999986 999999987 999999988 999999989 999999990 999999991 999999992 999999993 999999994 999999995 999999996 999999997 999999998 999999999 1000000000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
Output
14999999895

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。