オンサイトで未確認

ukuku09の活動記録。

UVALive 6070 - Conquer a New Region

簡単な問題しか解けない。マスコットだからね。

問題概要

頂点数 $N$ の木が与えられる。木の各辺には容量が設定されており、頂点 $u$ から頂点 $v$ へのスコアは $u-v$ パス上の辺の容量の最小値で定義される。

頂点 $w$ を一つ選んで、他の頂点から $w$ へのスコアの和を求めたとき、その最大値を答えよ。

解法

全方位木DPかと思ったけど、それでは無理だとbeetくんに教えてもらう。

辺を容量の降順でソートしておくと、辺 $i$ が2つの連結成分 $x,y$ を繋ぐとき、各連結成分に属する頂点に入るスコアはそれぞれ $size(y)*c_i,size(x)*c_i$ だけ増える。

連結性の管理と連結成分に属するすべての頂点に一度にスコアを加算するには、Union Findを応用してやると良さそうだと気づけば後は簡単。

 

giste2a3757a4faf918f4ea941df4138c4da