JOI 13春合宿 Spy(難易度8)
小課題2までは単純なDFSやLCAを求めるなどで解ける.
満点解法について考える.
まず, 木上で考えるのは難しいのでオイラーツアーでクエリを区間の問題に帰着する.
すると条件は二次元平面上に表現でき, クエリは長方形の追加に帰着できる.
よって, 二次元いもす法を用いて計算することでこの問題を
$ O(N^2)
で解くことができる.
実装例:
https://atcoder.jp/contests/joisc2013-day2/submissions/25843613