競技プログラミング総合スレ 64

競技プログラミング総 ..

842:デフォルトの名無しさん
22/12/20 12:42:02.98 GISGVI8J0.net
重み付きでも難しくないよまず適当に頂点を選んで、根にする
根からdfsをして、各頂点を根とする部分木のサイズを計算する(nums[v]: vを根とする部分木のサイズとする)
辺(u,v,w) (頂点uとvを結ぶ、重みwの辺)
が2点間の距離の総和(=sum(dist(u,v)) (1≤u<v≤N))に寄与する量は、
uとvの内、根から遠い方がvなら、w * (N-nums[v]) * nums[v]
根から遠い方がuなら、w * (N-nums[u]) * nums[u] になる
典型だから、ABCに転がってないか探したけど見当たらないな(CFならありそう)

次ページ

続きを表示

1を表示