点分治

概念：点分治每次选择重心作为分治中心，删除重心后各连通块大小不超过当前规模的一半。它适合统计经过某个中心的路径问题。

关键步骤

先计算子树大小，找最大连通块最小的结点作为重心；收集每棵子树到重心的路径信息，用已处理子树的数据统计跨子树答案，再递归处理各子树。

void getSize(int u,int fa){ sz[u]=1; for(int v:g[u])
    if(v!=fa && !dead[v]) getSize(v,u),sz[u]+=sz[v]; }
int getCentroid(int u,int fa,int tot){
    for(int v:g[u]) if(v!=fa && !dead[v] && sz[v]*2>tot)
        return getCentroid(v,u,tot);
    return u;
}
void solve(int entry){
    getSize(entry,0); int c=getCentroid(entry,0,sz[entry]);
    dead[c]=true; /* 统计经过 c 的路径 */
    for(int v:g[c]) if(!dead[v]) solve(v);
}

复杂度

分治深度 O(log n)，每层总处理 O(n)，典型时间 O(n log n)，空间 O(n)。统计时须避免把同一子树内路径重复计入。