問題と、その問題で使ったモノイドなどを記載していく
説明
いい絵がほしい
全方位木DPで求められるもの
各頂点を根としたときの木の高さ (演算: max, 頂点追加: +1)
言い換え: 各頂点に対して、その頂点から最も離れた頂点までの距離
特に木の直径や
木の高さの最小値
が求まる
各頂点を根としたときの木の頂点の数(演算: +, 頂点追加: +1)
どの頂点でも数は同じなので意味はない
問題例
ABC348 E - Minimize Sum of Distances
木の根を一つ固定したとき、距離*重みの総和を求める。(各頂点に対して、その頂点を根とした場合の計算結果を求める)