This folder contains crazy hard and creative Sqrt Decompostion, collected by me (Megumi Tadokoro).
http://acmp.ru/?main=task&id_task=647
http://codeforces.com/problemset/problem/455/D
[Hackerearth – Simple Tree Problem] (https://www.hackerearth.com/problem/algorithm/simple-tree-problem/)
[Polish Olympiad in Informatics XIV 2006-2007, Stage I – Queries] (https://szkopul.edu.pl/problemset/problem/MVjuhH4JZu17rusHweyEdyJx/site/?key=statement)
[Hackerearth – Benny and Sum] (https://www.hackerearth.com/problem/algorithm/benny-and-sum-2/description/)
https://www.spoj.com/problems/COT2/
https://codeforces.com/gym/100962/ - Problem F
https://www.codechef.com/problems/GERALD07
https://vn.spoj.com/PTIT/problems/OTOCI/
https://www.codechef.com/NOV14/problems/FNCS/
https://www.hackerrank.com/contests/hourrank-23/challenges/selective-additions/problem
http://codeforces.com/problemset/problem/1017/G (hint: Megumi's tree Decompostion)
http://codeforces.com/problemset/problem/1017/H
https://www.hackerrank.com/contests/w31/challenges/nominating-group-leaders
Sidenote: Megumi's tree Decompostion (created by Megumi Tadokoro (10/8/2018)
Brief description of Megumi's tree Decompostion (MD):
break the tree into forest of sqrt(n) trees, each of them has the size of at most sqrt(n). Then, we can do the queries by brute force. Also, the height of the subtree in decompostion is at most sqrt(n).