No.3755 Root for Your Route
Note: We have confirmed that AC is possible even in relatively slow languages such as PyPy, but we recommend submitting in a fast language such as C++.
Problem Statement
There is a tree with $N$ vertices numbered $1,2,\dots ,N$, and an integer $A_v$ is written on vertex $v$. ($A_v$ may be negative.)
The $i$-th edge connects vertices $u_i,v_i$ bidirectionally.
Bob and Alice choose vertices by the following procedure.
- Bob chooses $1$ vertex $r$.
- Alice chooses the start point $s$ and the end point $t$ of a simple path† containing vertex $r$, and moves along that path. ($s=t$ is allowed.)
Here, when moving along the simple path from $s$ to $t$, traversing the $k$-th edge takes Alice $k$ seconds.
Alice's score is defined as "the sum of the integers written on the vertices visited during the movement (including the endpoints), minus the total travel time."
Alice chooses $s,t$ to maximize her score,
and Bob chooses $r$ to minimize Alice's score.
Find Alice's score when both players act optimally.
† A "simple path" is a route formed by following, in order, vertices directly connected by edges, which does not pass through the same vertex $2$ or more times.
Constraints
- $2 \leq N \leq 10^5$
- $-10^9 \leq A_v \leq 10^9$
- $1 \leq u_i,v_i \leq N$
- The given graph is a tree.
- All input values are integers.
Input
The input is given from standard input in the following format.
$N$
$A_1\ A_2\ \dots\ A_N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$
Output
Output Alice's score when both players act optimally, on one line.
Sample
Sample 1
Input
5 6 -1 8 -2 6 1 2 2 3 2 4 4 5
Output
5
Suppose Bob chooses vertex $4$.
In this case, by moving from vertex $3$ to vertex $5$, Alice can obtain a score of
$
(8-1-2+6)-(1+2+3)=5
$
points.
No path through vertex $4$ gives a higher score than this.
On the other hand, if Bob chooses any of vertices $1,2,3$,
Alice can obtain
$(6-1+8)-(1+2)=10$ points by moving from vertex $1$ to vertex $3$.
Also, if Bob chooses vertex $5$,
Alice can obtain $6$ points by setting $s=t=5$.
Therefore, it is optimal for Bob to choose vertex $4$, and the answer in this case is $5$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
siganai