■ [AOJ]0575 : Festivals in JOI Kingdom 
想定解法と違う方法で解いたのでメモ。
解説スライドで、Union-Findを使った計算量 O(MlogN+QNα(N)) の30点解法が紹介されているが、これを平方分割を使って O(MlogN+Q√Nα(N)) にする。
N個のノードを距離が遠い順にソートして、√N個まとめてUnionする。
まだ答えが出ていないクエリのうちで、この√N個のノードをUnionする前後で繋がるようになったものだけを、もう一度今度はノードを1つずつくっつけながらどのタイミングで繋がるかを調べる。
Javaで普通にコレクション使って書いたら、GCまわりでMLEになったりTLEになったりした。最初に配列でバッファを取って使い回すように書き換えたら通った。
