noshi91

記事の review を担当する (+ 記事を書く) というのと異なる部分はありますか？

https://noshi91.github.io/algorithm-encyclopedia/larsch-algorithm#noredirect 現状です。ステートマシンを使わないと説明が困難なので、苦戦しています。

自由に根付き木にして、重心を毎回 1 から計算することにします。重心の内最も根に近いものを c とすると、c を根とする部分木の重みは全体の重みの半分を超えます (全体の重みが 0 の場合を除く)。部分木の重みは DFS pre-order で並べた列の区間和として表現されるわけですが、この列で左端から見て重みが半分になる位置 h を考えると、c についての区間は必ず h を含みます。よって、c の候補が根からのあるパス上に絞られました。 残りの部分ですが、HL 分解したときの light edge についてその辺の下の部分木の重みを管理しておくことが O(log(n)) でできるので、この情報を使って c がどの chain にいるかを O(log(n))...

Problem name should be 'Shortest Walk' rather than 'Shortest Path'. The shortest walk of an undirected graph containing negative edges is obvious, so there is no need to specify that...

これは analogue で自明なので準備の必要なしという close ですか？

- 各頂点と各辺について、それを含む $C _ 4$ の個数を数える

出力は整数なので良くて、内部で実数を使う時の精度を気にしているのだと思います。アルゴリズムを真面目に検討していないですが、整数範囲だけで書けるならそれでも良さそうです。

mod P で verify には足りそう、 $M$ は様子見ながらさらに大きくすることも考えている、ということで mod P にしたいと考えています。

All Composite か、セグ木無しでやりたいなら集合ハッシュを出力させるのが良いかなという気がします。

ランレングス圧縮で $a$ が $c$ 個あるとしたときの $\sum x _ a y _ c$ や $\sum x _ a ^ c$ を出力とかどうでしょうか。