ABC133-F:Colorful Tree - 思考の墓場

オイラーツアーとかはともかく、この解法が思いつけないのは悔しい...。

問題

解法

　まず、色の変更のことは忘れて、「木上の $2$ 点 $u,v$ 間の距離を求めよ。」というクエリに効率的に答えることについて確認する。このクエリに答えるには、 $u,v$ の最小共通祖先(LCA:Least Common Ancestor)が重要になる。木を $1$ を根とする根付き木だと思って、 $d(v)$ を頂点 $v$ の根からの距離とする。 $lca(u,v)$ を $u$ と $v$ のLCAとすれば、 $u,v$ 間の距離は $d(u)+d(v)-2d(lca(u,v))$ と書ける。つまり、 $u,v,lca(u,v)$ についての情報さえわかれば十分だということがわかる。LCAの効率的な述べ方については、ここでは省略するが、蟻本や検索をすれば情報は手に入るはず。
　色のことを思い出してみる。ある頂点 $v$ について「色 $x$ の辺の距離を $y$ に変えたときに、根からの距離を求めよ。」という問いに答える必要があるが、オンラインで答えるには若干の技術が必要になる(公式解説などはこれ)。ここでは、先にすべてのクエリの情報を読み込んでしまって、その上で各クエリの答えを求めることを考えてみる。まず、各頂点に「この頂点は $i$ 番目のクエリに関わり、そのクエリは色 $x$ の辺の距離を $y$ にしたときのことを聞いている。」という記録をしておく。そして根からdfsをして、mapなどのデータ構造などで、「今見ている頂点を $v$ として、 $v$ に着くまでに辿った各色の辺の距離の総和と本数」を管理しておく。 $v$ に来たら、保存していたクエリについて、mapのデータを参照しながら適切な計算を行う(現在の距離の総和から、色 $x$ の距離の総和を引いて、 $y\times$ (色 $x$ の本数)を足す)。 $v$ の子 $u$ に行くときは辺 $(v,u)$ の情報をmapに追加し、 $u$ から帰ってきたら辺 $(v,u)$ の情報を破棄すれば、全体を $1$ つのmapで処理することができ、空間計算量が $O(N+Q)$ で済むようになる。時間計算量は $O((N+Q)\log{N})$ である。