树剖:

https://ac.nowcoder.com/acm/problem/20449

https://ac.nowcoder.com/acm/problem/18939

cdq分治:

https://ac.nowcoder.com/acm/problem/19881

点分治:

https://www.luogu.com.cn/problem/P4886

https://codeforces.com/contest/321/problem/C

https://ac.nowcoder.com/acm/contest/11171/D

dsu on tree:
https://www.luogu.com.cn/problem/CF375D
https://nanti.jisuanke.com/t/42586