No.3660 LIS on Tree
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
くらげ
sepa38