树分治

# Notes [点分治详解 - Ying xue Cat](https://www.cnblogs.com/ying-xue/p/17077989.html)：最适合入门的一篇，详细地展示了从暴力优化到点分治核心思想的过程。一针见血地，“使用点分治的前提条件是我们不那么关心树的具体形态，比如 路径、连通块 相关的问题”。 [点分治学习笔记 - Menci](https://oi.men.ci/tree-divide-notes/) [树分治小记 - command_block](https://www.luogu.com.cn/blog/command-block/shu-fen-zhi-xiao-ji) [边分治 - JZP 的博客](https://www.luogu.com.cn/blog/jzp1115/bian-fen-zhi) [边分治讲解 - JhinLZH](https://www.cnblogs.com/Khada-Jhin/p/10154994.html) [[学习笔记]边分治 - *Miracle*](https://www.cnblogs.com/Miracevin/p/10430208.html) [https://www.luogu.com.cn/blog/221955/shu-fen-zhi-zong-jie-dian-bian-fen-zhi-dian-bian-fen-shu-post](https://www.luogu.com.cn/blog/221955/shu-fen-zhi-zong-jie-dian-bian-fen-zhi-dian-bian-fen-shu-post) [树分治——边分治与边分树 - 一粒夸克](https://www.cnblogs.com/A-Quark/p/15806692.html) [lazytag 的边分治笔记](https://lazytag.blog.luogu.org/bian-fen-zhi-xue-xi-bi-ji) # Problems ## 点分治 ### 点分治入门1 P3806, P4178, P4149, P6626, P5351, CF293E ### 点分治入门2 P5306, P3060, P6326, P7215, P5306, P8949, P8123, P7565, P4886, [HDU5909 Tree Cutting](http://acm.hdu.edu.cn/showproblem.php?pid=5909) ### 点分治入门3 P2664, CF566C, P4183, P9678, P5439, CF786D, P7126, [gym102538G Giant Penguin](https://codeforces.com/gym/102538/problem/G), [QOJ#7086. Inner Product ](https://qoj.ac/problem/7086) ### 点分治与单调队列按秩合并 P3714, CF150E, P4292 ### 点分治与虚树 P6668, P4565, P6668, CF772E ### 点分治与字符串 CF914E, P4075 ### 点分治优化 MST(trick) AT_cf17_final_j, P6199 ### 点分治与古河渚 CF434E Furukawa Nagisa's Tree 打赢复活赛了 ## 点分树 & 动态点分治 [AT_abc291_h](https://www.luogu.com.cn/problem/AT_abc291_h), P6329, P2056, P3676, P3241, P3345, P5912, P5311, CF936E, P6541, P3920, [gym101234D Forest Game](https://codeforces.com/gym/101234/problem/D), [gym102538A Airplane Cliques](https://codeforces.com/gym/102538/problem/A), [HDU6844 Animism](https://acm.hdu.edu.cn/showproblem.php?pid=6844) ## 边分治 & 边分树 ### 边分治入门 P2056, P3241, CF833D, P6670 ### 边分治与合并凸包 P5114, CF1019E ### 边分树入门 P3241 ### 边分树合并 P4220, P4565 ### 可持久化边分树 CF757G ## 杂题 P5984, P9260, [gym102391K Wind of Change](https://codeforces.com/gym/102391/problem/K), [QOJ# 2564. Two Trees](https://qoj.ac/problem/2564), [QOJ# 4815. Flower's Land](https://qoj.ac/problem/4815), [AT_icpc2016autumn_k Non-redundant Drive](https://www.luogu.com.cn/problem/AT_icpc2016autumn_k)