ABC214 D - Sum of Maximum Weights (400)
木なので二つの頂点を結ぶ各辺を二度以上通らないパスは一通り
重みの大きい辺から順にその辺の左の頂点の数とその辺の右の頂点の数の積がその辺の使われる数になる
その後その辺を消して木を分割する
これだと計算が大変なので重みの小さい辺から考える
小さい辺から使って頂点を結合していく
左の連結成分のサイズと右の連結成分のサイズの積がその辺の使われる数
連結成分はUnionFindで効率的に求まる
問題:
https://atcoder.jp/contests/abc214/tasks/abc214_d
提出:
https://atcoder.jp/contests/abc214/submissions/25036481
#ABC214
#400pt
#D
#ABC
#AtCoder
#木
#UnionFind