No.3755 Root for Your Route
marc2825
siganai注意： PyPy などの比較的低速な言語でも AC 可能であることを確認していますが、 C++ などの高速な言語での提出を推奨します。
問題文
頂点 $1,2,\dots ,N$ の $N$ 頂点からなる木があり、頂点 $v$ には整数 $A_v$ が書かれています。（ $A_v$ は負の場合もあります。）
また、 $i$ 番目の辺は頂点 $u_i,v_i$ を双方向に結んでいます。
Bob と Alice は、次の手順で頂点を選びます。
- Bob が頂点 $r$ を $1$ つ選ぶ。
- Alice が、頂点 $r$ を含む単純パス†の始点 $s$ と終点 $t$ を選び、 そのパスに沿って移動する。($s=t$ でもよい。)
ここで、 $s$ から $t$ への単純パスに沿って移動するとき、 Alice の $k$ 本目の辺の移動には $k$ 秒かかります。
Alice の得点を、「移動中に訪れた頂点（端点含む）に書かれた整数の総和から、
総移動時間を引いた値」とします。
Alice は得点を最大化するように $s,t$ を選び、
Bob は Alice の得点を最小化するように $r$ を選びます。
両者が最適に行動したときの Alice の得点を求めてください。
† 「単純パス」とは、辺で直接結ばれた頂点を順にたどってできる経路であり、 同じ頂点を $2$ 度以上通らないものをいいます。
制約
- $2 \leq N \leq 10^5$
- $-10^9 \leq A_v \leq 10^9$
- $1 \leq u_i,v_i \leq N$
- 与えられるグラフは木
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
$N$
$A_1\ A_2\ \dots\ A_N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$
出力
両者が最適に行動したときの Alice の得点を一行で出力してください。
サンプル
サンプル1
入力
5 6 -1 8 -2 6 1 2 2 3 2 4 4 5
出力
5
Bob が頂点 $4$ を選んだとします。
このとき Alice は、頂点 $3$ から頂点 $5$ まで移動することで、
$
(8-1-2+6)-(1+2+3)=5
$
点を得られます。
頂点 $4$ を通るどのようなパスを選んでも、これより大きな得点は得られません。
一方、Bob が頂点 $1,2,3$ のいずれかを選ぶと、
Alice は頂点 $1$ から頂点 $3$ まで移動することで
$(6-1+8)-(1+2)=10$ 点を得られます。
また、Bob が頂点 $5$ を選ぶと、
Alice は $s=t=5$ とすることで $6$ 点を得られます。
したがって Bob は頂点 $4$ を選ぶのが最適であり、このときの答えは $5$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。