やぶについて書きます
はじめに
これは Competitive Programming Advent Calendar 2016（その2）の 18 日目の記事です． 内容はやぶについてです．
内容
近所にあるやぶそばというお店はとても美味しいです．僕のオススメはもつ煮込み定食(800円)とメンチそば定食(750円)です． 明日はdohatsutsuさんの「未定です」とminus3thetaさんの「おまけのような話を書きます」です．とても楽しみですね！
ところで
UnionFindって知ってますか？僕は知ってます(ごめんなさい，初心者向けにしようと思ったんですがここまで解説する暇がありませんでした，蟻本を読もう！！)1．
つづき
UnionFindは $v$ が属する木の根を爆速で求めるものでした．似たようにして，ある過去の時点において $v$ が属していた木の根を求める，というクエリにも答えられないでしょうか？1 これは割と簡単にできます．
おまけ
データ構造をマージする一般的なテク(Weighted Union Heuristics)って知ってますか？僕は知ってます(ごめんなさい，初心者向けにしようと思ったんですがここまで解説する暇がありませんでした，“データ構造をマージする一般的なテク”とはを読もう！！)1
この前 CF383 Div1 D の想定解としてツリー上でマージテクするやつの亜種みたいなものが紹介されました．UnionFindつながり，ということでこれも紹介します．
まとめ
- やぶはとても美味しい
- UnionFindって知ってますか?僕は知ってます
- 普通のUnionFindをちょっといじるだけで部分永続UnionFindにできます
- 木上でデータ構造をマージする一般的なテクは定数倍改善できる場合があります
- 明日はdohatsutsuさんの「未定です」とminus3thetaさんの「おまけのような話を書きます」です．とても楽しみですね！
