前言
模拟赛T2要用点分，于是花了一晚上学了一下，结果还是搞不掉T2
正文
点分是一种树上分治思想，以某点为分治点，对其子节点进行分治，最后再回收统计答案。
1.找分治点
寻找树的重心做为分治点，如果选的不是重心，当图为一条链时，复杂度退化，由O(n log n )退化至O(n^2)
2.分治
递归至子节点，对子节点重复操作，至到到达叶节点
3.回收统计答案
因题而异，自行把控
例题
点分治学习笔记
发布时间 2023-03-22 21:13:12作者: 蒻蒟cdx
模拟赛T2要用点分，于是花了一晚上学了一下，结果还是搞不掉T2
点分是一种树上分治思想，以某点为分治点，对其子节点进行分治，最后再回收统计答案。
寻找树的重心做为分治点，如果选的不是重心，当图为一条链时，复杂度退化，由O(n log n )退化至O(n^2)
递归至子节点，对子节点重复操作，至到到达叶节点
3.回收统计答案
因题而异，自行把控