Quiz
- https://yukicoder.me/problems/no/778
- 0を根とする木にて、a<bかつaがbの先祖である個数を数えよ(N=200000)
AC Code (BIT ver)
AC Code (Euler Tour ver)
はじめに
- https://betrue12.hateblo.jp/entry/2019/06/22/195307
- こちらを読めば、すべてが分かります。感謝
この記事は何?
- 木のdfs, オイラーツアーが分かったぞ記念、のメモです(。>﹏<。)
Note
感想
- BITは数えるのに優秀
- オイラーツアーを実際に使ってみて、その頂点が最初に出てきた位置、最後に出てきた位置を保存しておく必要性を体感できた