没错...我就是要讲点分治。这个东西原本学过的，当时学得不好...今天模拟赛又考这个东西结果写不出来。

于是博主专门又去学了学这个东西，这次绝对要搞懂了...【复赛倒计时：11天】

——正片开始——

点分是一个用来解决树上路径问题、距离问题的算法。说直接点其实就是分治思想在树上的体现和应用。

首先是分治的方法，既然是树上问题，自然就是对树进行分治。

我们对于一棵树，选定一个点作为它的根，将这个点与其子树拆开，然后对它的子树也进行相同的操作，然后利用子树统计答案。一般来说，点分更像一种思想，而不是一个算法，当然你也可以把它当算法来学。

关于怎么选根来分树，其他dalao的博客已经讲得非常清楚仔细了，每次选定一棵树的重心，然后分它，这样可以做到

O(nlogn)的优秀时间复杂度。

关于求重心，做法就是一个size统计。

这里还是介绍一下吧（很多博客都只贴一个代码...):
对于一个节点x，若我们把其删除，原来的树就会变成若干部分，我们设maxsubtree(x)表示删除x后剩下的最大子树的大小，若我们找到一个x，使得maxsubtree(x)最小，x就是这棵树的重心。

给出求重心的代码：

void getroot(int x,int fa){     siz[x]=1;son[x]=0;     for(int i=head[x];i;i=nxt(i)){         int y=to(i);         if(y==fa||vis[y])continue;         getroot(y,x);         siz[x]+=siz[y];         if(siz[y]>son[x])son[x]=siz[y];     }     if(Siz-siz[x]>son[x])son[x]=Siz-siz[x];     if(son[x]<maxx)maxx=son[x],root=x; }

于是我们就知道怎么拆树了，后面的东西就不难了。

update: 19.11.5 对于上面的代码加一些解释，Siz表示当前在求重心的这一棵树的大小，root用来记录重心

我们来讲如何统计信息

首先我们要统计与每一次找到的重心有关的路径，我们用dis[x]表示目标点（重心）到x的距离。

给出getdis的代码：

void getdis(int x,int fa,int d){//d表示x到目标点的距离    dis[++top]=d;//我们只需要知道每一个点到目标点的距离就行，不用知道这个点是哪个    for(int i=head[x];i;i=nxt(i)){         int y=to(i);         if(y==fa||vis[y])continue;         getdis(y,x,d+val(i));     } }

有了dis数组后，我们就可以很轻松的获得路径的长度了。

比如，我们已知x到重心的距离是m，y到重心的距离是n，那x到y的距离就是m+n，可能细心的读者已经发现锅了。

如果x到y的路径都在一棵子树内，我们就会有一段距离被重复计算了，这样我们得到的路径就是不对的。

给一张图理解一下：
如图，蓝色的代表x到重心的路径，红色的代表y到重心的路径，我们可以得到dis[x]=3，dis[y]=2。

如果按照前面说的计算方式，x到y的路径长度应该是5了，但是并不是，我们的路径长度是3。

原因就是，绿色的那一段，我们根本不走，我们不经过它。

于是我们要解决这种不合法路径。知道所有路径，又知道不合法路径，利用容斥原理，我们可以得到：