点分治

点分治用来处理树上路径问题，每一次将树分治为几棵子树，然后继续递归，得到答案

每次分治时，子树的根选取为其的重心，递归的子树大小不会超过原树大小的一半，保证了时间复杂度为O(n\ log\ n)

利用容斥原理统计答案

树上有多少对点，满足两点间的距离小于等于k

void dfs_root(int x,int fa)
{
    siz[x]=1,ma[x]=0;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(vis[y]||y==fa) continue;
        dfs_root(y,x);
        siz[x]+=siz[y];
        ma[x]=max(ma[x],siz[y]);
    }
    ma[x]=max(ma[x],tot-siz[x]);
    if(ma[x]<ma[root]) root=x;
}
void dfs_dis(int x,int fa)
{
    len[++len_cnt]=dis[x];
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to,v=e[i].v;
        if(vis[y]||y==fa) continue;
        dis[y]=dis[x]+v;
        dfs_dis(y,x);
    }
}
int calc(int x,int lenth)
{
    len_cnt=0,dis[x]=lenth;
    dfs_dis(x,0);
    sort(len+1,len+len_cnt+1);
    int sum=0,l=1,r=len_cnt;
    while(l<r)
    {
        if(len[l]+len[r]<=k) sum+=r-l,l++;
        else r--;
    }
    return sum;
}
void solve(int x)
{
    vis[x]=true,ans+=calc(x,0);
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to,v=e[i].v;
        if(vis[y]) continue;
        ans-=calc(y,v);
        root=0,tot=siz[y];
        dfs_root(y,0);
        solve(root);
    }
}

......

tot=ma[0]=n;
dfs_root(1,0);
solve(root);

动态点分治

需要支持修改时，考虑用动态点分治解决

通过构建一棵点分树，然后在点分树上修改，通过不断向上来跳父亲来维护信息

点分树为点分治时每一层的重心之间连边的一棵树，高度为log\ n

捉迷藏：给定一棵树，树上的点为黑色或白色，初始都为黑色，支持修改颜色和询问两个距离最远的黑点的距离

维护三个堆：

void dfs_root(int x,int fa)
{
    size[x]=1,ma[x]=0,s[++cnt]=x;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(vis[y]||y==fa) continue;
        dfs_root(y,x);
        size[x]+=size[y];
        ma[x]=max(ma[x],size[y]);
    }
    ma[x]=max(ma[x],tot-size[x]);
    if(ma[x]<ma[root]) root=x;
}
void solve(int x)
{
    vis[x]=true;
    q2[x].push(0);
    for(int i=1;i<=cnt;++i)
        q3[x].push(dis(fa[x],s[i]));
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(vis[y]) continue;
        root=cnt=0,tot=size[y];
        dfs_root(y,x);
        fa[root]=x,y=root;
        solve(root);
        q2[x].push(q3[y].top());
    }
    q1.push(q2[x].len());
}
void modify(int x,int type)
{
    q1.del(q2[x].len());
    if(type) q2[x].del(0);
    else q2[x].push(0);
    q1.push(q2[x].len());
    for(int i=x;fa[i];i=fa[i])
    {
        int l1=q3[i].top(),l2,dist=dis(fa[i],x);
        if(type) q3[i].del(dist);
        else q3[i].push(dist);
        l2=q3[i].top();
        q1.del(q2[fa[i]].len());
        if(l1!=-inf) q2[fa[i]].del(l1);
        if(l2!=-inf) q2[fa[i]].push(l2);
        q1.push(q2[fa[i]].len());
    }
}

点分树树高为 log\ n，所有点的子树和为 n\ log\ n