Codeforces Round #627 (Div. 3) F - Maximum White Subtree

F - Maximum White Subtree

問題概要

木に黒白の色が割り当てられていて、ある頂点を含む部分グラフにおいて白の数と黒の数の差を最大化してください。

解説

rerootingという概念らしいです。まず根が0も場合についてdpをします。この計算自体はO(N)で終わりますが、他の根の場合には、同じ計算量がかかるとO(N^2)になり間に合いません。ここで、一度のO(N)の計算でdpを埋めた後、rerootingによって速い計算で更新を行うことを考えます。

根が1の状態がわかっていると、その子の値は簡単なつなぎかえで実現できます。そこからdfsにより再帰的に計算していくと、全ての根について高速に求めることができます。

ある根からdpを埋めるのにO(N)、そこから全ての根について更新するのにO(N)かかります。