問題一覧 > 通常問題

No.3755 Root for Your Route

レベル : / AI推定難易度 : 2425 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 3
作問者 : marc2825 / テスター : siganai
お気に入りにしたユーザー ProblemId : 13786 / 自分の提出
問題文最終更新日: 2026-08-29 00:56:35
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
yukicoder contest 516 (順位表) の他の問題:

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.

  1. Bob chooses $1$ vertex $r$.
  2. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。