概要 https://dic.kimiyuki.net/d-edge-shortest-path-monge この記事においてラグランジュ双対などで説明した部分を凸共役の観点から解釈し、「 本以上 本以下使う最短路」も同じように解くことができることを解説します。 本文 合成積 関数 の合成積 は \b…

注意: 雑です 概要 [1] で定義された top tree は、葉が underlying tree の辺に対応するなどの条件があります。 [2] は splay tree をベースにした top tree を説明しています。 [1] の定義にはわずかに合致しないものの、いくらかの良い性質を持つ構造を思…