ひとり言

Codeforces Round #527 (Div. 3)F. Tree with Maximum Cost

問題概要

$n$ 頂点の木が与えられる. 頂点 $i$ には値 $a_i$ が割り当てられている. 頂点 $v$ に対し関数 $f$ を

$f(v) = \sum_{i=1}^{n}dist(i, v)\times a_i$

と定義する. $v$ を自由に選べるとき, $f(v)$ の最大値はいくらか？

問題へのリンク

制約

$1 \le n \le 2\times 10^5$
$1 \le a_i \le 2\times 10^5$

解法

典型的な全方位木dpの問題です. 全方位木dpがわからない方はまずググってください.

最初に部分木についての問題を解きましょう. これは普通に木dpをすればいいです. $val_v :=$ (頂点 $v$ の部分木についての $f$ の値), $sum_v :=$ (頂点 $v$ の部分木にある頂点についての $a$ の総和) という風に定義すれば, 頂点 $p$ についてその $val_p$ の値は, 全ての $p$ の子頂点 $v$ について $val_v + sum_v$ を足しあげた値になります. これは, 子頂点の $f$ に加え, $p, v$ 間の辺を通ることによって加算される量が $sum_v$ に等しいことを利用しています(実験してみてください).

ここまでできればあとは全方位木dpするだけです. $ans_p$ を頂点 $p$ の最終的な答えだとすれば, その子頂点 $v$ の答えは

$ans_v = val_v + ans_p - (val_v + sum_v) + allsum - sum_v$

です( $allsum$ は $a_i$ の総和です). 自分の部分木の答え(第 $1$ 項)に加え, 自分の親頂点の答え(第 $2$ 項)から自分の部分木の影響(第 $3$ 項)を除いた後, 親頂点を自分の部分木としてマージする係数(第 $4, 5$ 項)がついてこの式になります.

あとは適当に dfs すればおしまいです.

実装

Submission #146591764 - Codeforces