在面对树上路径的处理问题中，我们有一个十分方便的离线处理方法点分治。

点分治的构成具体如下

1.找重心

2.计算（单个重心）子树答案

3.合并答案

很方便对吧。

让我们一个一个讲

以这题为例题目让我们求一棵树中简单路径距离<=k的点对数。

1.找重心

重心是什么——一个树当中，最大的子树最小的节点便是重心，要注意的是重心不一定唯一，但取任意一个是没有影响的，实际上你取任意一个子树内点对答案都没有影响，只是效率不同而已，几乎所有点分治的题目这一步都是一样的，至于为什么几乎，因为我刷题量少不知道会不会有特例。

inline void Get_rt(int now,int fa,int Size)
{
    size[now]=1;int Max_size=0;
    for (int i=head[now];i;i=e[i].next)
    {
        int v=e[i].to;
        if (vis[v]||v==fa) continue;
        Get_rt(v,now,Size);
        size[now]+=size[v];
        Max_size=max(size[v],Max_size);
    }
    Max_size=max(Max_size,Size-size[now]);
    if (Minn>Max_size) rt=now,Minn=Max_size;
}

2.计算（单个重心）子树答案

这个也很简单，dfs一遍以后直接将重心到子树内所有点的距离求出，然后sort以后双指针移动就好了，代码里的val先不用管，第三步会说。总而言之就是将两条路径并成一条算贡献。

inline int solve(int rt,int val)
{
    l=1,r=0;
    int ans=0;
    len[rt]=val;
    Get_dis(rt,rt);
    sort(D+1,D+r+1);
    while (l<r)
    {
        if (D[l]+D[r]<=K) ans+=r-l,l++;
        else r--;
    }
    return ans;
}

3.合并答案

这个要细讲，相信前面读者应该就有疑惑了，那如果出现这种情况怎么办呢。

这样的话我们在合并子树答案时就需要减去重心与其直系儿子路径的贡献，所以上一步中有一个val，至于为什么是重心与其直系儿子，因为重边必经这里。然后就是简单的容斥。

inline void Get_Ans(int now)
{
    vis[now]=1;
    Ans+=solve(rt,0);
    for (int i=head[now];i;i=e[i].next)
    {
        int v=e[i].to;
        if (vis[v]) continue;
        Ans-=solve(v,e[i].dis);
        Minn=2e9;
        Get_rt(v,v,size[v]);
        Get_Ans(rt);
    }
}

就这样，点分治的模板题就被我们解决了。

点分治的核心在于分治重心，所以时间复杂度为$ O(nlogn) $有兴趣的可以自己证下。

update2020.5.31 草写点分树的时候发现自己的点分治一直是写假的(但是复杂度正确性都可以保证)，然后今天看到这篇博客，如果对我有疑惑的人可以看看这一篇博文。