kujira16 https://blog.hatena.ne.jp/kujira16/ くじらにっき++ https://kujira16.hateblo.jp/ 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2667 解法 クエリをB個ごとのブロックに分割する。ブロックのはじめにやる処理をSetUp，ブロックのおわりにやる処理をTearDownと呼ぶことにする。 SetUp ブロック内のクエリで関係する頂点だけを使って，縮約されたO(B)頂点の森を作る。ブロック内のクエリで関係する頂点とは，具体的には以下のとおり。 addクエリで指定された頂点v distanceクエリで指定された2つの頂点u, vとLCA(u,v) この処理はO(N)でできる。 クエリ処理 addクエリ add… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkujira16.hateblo.jp%2Fentry%2F2015%2F11%2F06%2F193526" title="AOJ 2667 Tree (クエリ平方分割解法） - くじらにっき++" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=B%3DO%28%5Csqrt%7BQ%7D%29 Hatena Blog https://hatena.blog 2015-11-06 19:35:26 rich https://kujira16.hateblo.jp/entry/2015/11/06/193526 1.0 100%