[算法xio讲堂]点分治
点分治
感觉点分治不怎么难可能是我太弱了，算了。不BB了。
定义
所谓点分治，就是基于点来做分治。而分治是分而治之的意思，比如说我们有一群范围非常大的的问题，但是这些问题都有一些相似的特性，那么我们就按照这个特性来分掉这些问题，然后对于每一个问题都按照相似的处理方式，得到最小的答案，然后将小的答案按照某种方式算出整个问题的答案。像这种求解的方法就叫做分治。
其实沃认为点分治更像是一种高级暴力（逃跑）
回归正题，那么在一棵树上也是同一个道理，将一棵树分成一棵棵的小树，然后对每一棵树进行操作。
那么像这种方法求解树上的问题，一般都能至少降低一个\(log\)级别的复杂度，但是更多的都是将复杂度从\(O(n^3)\)降到\(O(n^2)\)，这样我们的程序就会避免遍历一些重复的状态，从而减少运算的次数。
原理（基于重心的分割）
首先点分治作为一种高效搞笑算法，需要全面的考虑任何的退化情况。对于树上的特殊情况有三种：菊花图，链，和菊花链，这三种情况最有可能会让树上的算法退化时间复杂度。
但是对于点分治来说还是链的影响更大一点，那么我们想一下如何将分治掉这条链。
非常明显，将这条链二分比较的好，但是对于一般的问题我们又应该怎么平均分呢？
这个时候我们引入一个新的概念叫做重心。
所谓重心，就是在这棵树中最重的地方，准确的定义是：最大的子树后辈节点个数最少的节点叫做重心。
为什么要引入这个概念，因为树的重心能把一棵树尽可能地平均分配。
\(ps.\)重心有一个比较神奇的性质：每一个子树的大小都不超过n/2
关于重心性质的证明
考虑有如上这么一棵树，其中\(u\)是重心，\(son[u]\)表示\(u\)点的最大的子树的大小，\(v\)是点\(u\)的最大子树，且\(size[v]>\frac{size[u]}{2}\)。
因为\(size[v]>\frac{size[u]}{2}\)，其他子树加上点\(u\)的节点数小于\(\frac{size[u]}{2}\)，那么不难发现，我们选择点\(v\)作为重心，\(son[v]=size[v]−1<son[u]\)，那么很明显\(u\)不满足重心的定义。
举一个例子：（(●’◡’●)）
像这棵树的重心就是\(4\)号点，这棵树中\(4\)号点最大子树后辈节点个数为\(11\)，是整棵树上的所有节点中最小。也说明了这个节点能尽可能平均地分割这棵树。
求解重心的代码
void getroot(int u,int fa){
sz[u]=1; mxs[u]=0;//sz数组是子树的节点个数，mxs是maxson的缩写，表示的是最大的子树的节点数
for(int e=H[u];e;e=E[e].nt){//前向型的遍历方式
int v=E[e].to;
if (v==fa) continue;//如果遇到了父亲那么就跳过
getroot(v,u);//向下递归求解
sz[u]+=sz[v];
mxs[u]=max(mxs[u],sz[v]);//计算mxs
}
mxs[u]=max(mxs[u],sum-sz[u]);//这是另外一半的树，这也是这棵树的子树（整棵树被当作了无根树）
if(mxs[u]<mxs[rt]||rt==0) rt=u;//判断是不是重心
}有位大佬的博客上写了一些不同的看法：传送门
“分而治之”的“治”操作
这个比较难讲清楚，我尝试一点一点来将问题讲清楚。
我先贴出一个伪代码，让大家了解一下
void divide
计算当前全局的答案
记录访问节点
枚举子节点{
如果访问过就跳过
将局部重复解减去
递归搜索子树重心
}首先对于点分治的答案计算需要一点容斥原理的知识，我们以某谷的模板题为例：传送门
void solve(int u){
calc(u,1,0);//计算答案
vis[u]=1;//标记已经访问过了
for(int e=H[u];e;e=E[e].nt){
int v=E[e].to;
if(vis[v]) continue;//如果已经访问过了就不用访问了，也起到了不算父亲的情况
calc(v,0,E[e].w);//容斥原理减去所有重复的状态
MX=inf; sum=sz[v]; rt=0; getroot(v,-1);//算出子树的重心
solve(rt);//递归求解
}
}第一次看到别人blog的时候，我也是非常懵逼的？但是理解起来还是比较简单的，其核心是容斥原理：在扯一点题外话：所谓容斥原理就是在计算问题是有重复的部分，我们先将所有的部分全部都算出来，这样在将多出来的重复部分减去，保证答案的正确性。
那么对于树上点分治有什么需要容斥原理的地方，很明显：假设我们要计算的答案是\(ans1=getans(rt->u->v1)\)，那么也会算出\(ans2=getans(rt->u->v2)\)，其中的\(v1\)和\(v2\)都是\(u\)的儿子，因为要保证答案的正确性，那么我们一定是要将\(ans1\)和\(ans2\)加起来，或者是其他的整合操作，但是这个时候我们需要考虑一个问题，整合时候\(rt->u\)这一部分的答案是不是算了两边，也就是容斥原理中所说的重复部分。有人会问：为什么会重复？这个不是树上的操作？不是一般都不会有重复的吗？不然\(dfs\)暴力求解怎么做？有人这样问我。请在看一下我们的程序框架，我们是算出答案后在计算分治求解接下去的答案。
那么为什么不能先递归下层节点，在计算答案？因为下层的答案是由上层的答案求出的，这和其他的树上操作有一点不一样，不然求出的答案就会只有部分解。
那么回归正题，我们来举一个例子更生动地理解一下，再次清楚我们的的图片君，