典型寄せ集めみたいな問題
解説
まず、道の本数が高々 本なので、作れる道を列挙できれば、クラスカル法で空港の数と道のコストの組を計算できる。
空港の建設コストは会社ごとに異なるので、これを変数だと考えると、上に挙げた組は一次関数になり、最小値は Li Chao Tree や Convex Hull Trick で求められる。
あとは道の列挙方法だが、道が 軸か
軸に平行であることを考えれば、Segment Tree で平面走査してやればよい。
実装は重めだが、ad-hoc な実装がなくてパートごとに分けやすいので、そこまでバグは埋めにくいかと思う。
時間計算量は になる（たぶん）。
