問題ページ これは を最小化するように空港を設置する問題である．もし と が同じ木の頂点であれば，どのように空港を配置しても2点間の距離は変化しない．木の2点間の距離はLCAなどを用いることによって で求めることができる． ここからは と が違う木に属…

問題ページ が の中央値のとき は最小になる．Wavelet Matrixを用いると数列のある連続する区間のk番目の数を求めることができるので，各クエリに対して中央値を求めることができる． 未満の要素の個数 未満の要素の和 以上の要素の和 以上の要素の個数 が答…