これまでに出てきた`a`の中央値で$f(x)$が最小値を取ることが分かる。queueを2個使って、小さい`a`と大きい`a`をそれぞれに格納しておく。queueにとても小さな数ととても大きな数を入れておくと、queueが空の場合の処理をはしょれる。Treehttps://atcoder.jp/contests/past-sample/tasks/abc133_f「アルゴリズム」実技検定ではあるけれど、ダイクストラとか最長共通部分列を求めるとか、教科書に出てくるアルゴリズムをそのまま使うような問題はAtCoderではあまり出てこない。このくらいの難易度になると、良く知られたアルゴリズムを道具として一部で使うとか、一工夫を加えて使うとかする問題が出てくる。問題を作る側も、良く知られた問題に一ひねりを加えて問題を作ることがあるので、解くほうはその一ひねりをどう対処するかを考えれば良いのだろうか。一ひねりによって全く違う問題になることもあるのだけど。木が与えられて、頂点`x`と頂点`y`の距離を何度も聞かれる問題では、[最小共通祖先](https://en.wikipedia.org/wiki/Lowest_common_ancestor)を使う解法が知られている。頂点`u`と頂点`v`の最小共通祖先とは、頂点`u`と頂点`v`の共通の祖先で、根から最も遠いものである。前処理として、ある頂点を根にして、そこからの距離を求めておく。この問題の一ひねりは、辺の長さが変わることである。各頂点で、各色について、その色の辺の個数と合計長を記録しておけば辺の長さの変化にも対応できる。色は最大で`N-1`なので、全ての色について記録しておくのは無理である。考えてみると、全ての頂点で全ての色が必要なわけではない。その頂点を対象とするクエリ、もしくはその頂点を最小共通祖先として参照するクエリの色だけを覚えておけば良い。この手の問題では律儀に前処理を終えてからクエリを読む必要はないということが重要。最初にクエリを全部読んで、それからクエリに応じた前処理を行っても良い。998244353で割った余りを出力してくださいサンプル問題では初めて出てきたけれど、この割った余りを出力してくださいというのは競技プログラミングで良く出てくる。言語によっては多倍長整数が無く、64ビットより大きい整数を扱うのが大変なので、扱う整数を64ビット以下に収めたいらしい。`M=998244353`として、足し算、掛け算は、計算するごとにそれぞれ`(a+b)%M`、`a*b%M`とすれば良い。引き算は、C++の場合負の数の剰余が負になるので、`(a-b+M)%M`としなければならない。Pythonならば結果が0以上となるので、`(a-b)%M`で良い。割り算は、逆数を掛ける。M$となるような$b$。M$なので、$b=a^{M-2}$となる。冪乗は[こんな感じ](https://github.com/kusano/proconlib/blob/master/powmod.cpp)で高速化できる。$x^{20}=x^{16}x^4$。サイズ$N$の集合$S$の空集合ではない部分集合は$2^N-1$個ある。10^5$の制約下で律儀に計算するのはどう考えても無理である。ひっくり返して、「各点について、その点を含むような部分集合は何個あるか?」を考える。これも大変なので、さらに補集合を考え、「各点について、その点を含まないような部分集合は何個あるか?」とする。これはその点について、全ての点がその点の上下左右いずれかだけにある部分集合である。2回数えているので、その分を引く。Tree(BIT)を組み合わせるとできる。「アルゴリズム」実技検定っぽさが出てきた。