University CodeSprint: Counting On a Tree

列の問題を解くことを考える。

区間 x と区間 z に対して処理をしたい。F(x) は区間 x に対して頻度をベクトル化したもの。F(x)F(y) は内積を取っている。

よく考えると、下図のように分解できる。

f:id:pekempey:20161114024830p:plain

これを木に拡張すればいい。

本質的な部分はこれだけだが、場合分けがひたすら面倒。区間の交わり方は上で紹介した以外に 2 通りある。

さらに面倒なのは、i≠jという制約で、これがなければそこまで辛いとは思わなかったかもしれない。といっても、パスの共通部分の個数を引いておけば良いのだけど。

オイラーツアーをすれば木でも Mo's algorithm は使える。クエリを適切に前処理できれば、Mo のパートは簡単。

HL分解を貼ってるけど、LCA と k 個上の頂点を求める以外には使っていない。

（変更 2016/11/14 05:02）分解パートの場合分けが大分減らせた。機械的に減らしたので分かりにくいかも。元の場合分けが見たければRevisionsを見てください。

場合分けが多くて辛かった。