树的重心与直径 - NOI提高级教程

📖 算法原理：重心的最大子树极小化与直径双搜定理

在无环连通图——树（Tree）中，重心和直径是其最核心的两个拓扑几何量：

📐 树的重心（Centroid）定义与性质

重心是树上的一个节点 $u$，满足删去 $u$ 后，分裂出的所有子树中最大子树的大小最小。

求解方法：任选一点作为 DFS 树根。在递归回溯过程中，动态统计以每个节点 $i$ 为根的子树大小 $size[i]$。则删去 $i$ 后最大连通块的大小为 max_size[i] = max(N - size[i], max(size[children]))。全局遍历求出该值最小的节点即为重心。
重要性质：树的重心至多有 2 个。若有 2 个，则它们必直接相连，且删除它们后两个部分的节点大小均为整个树的 $N/2$。

📐 树的直径（Diameter）定义与双重 DFS 定理

直径是树中任意两个节点之间最长简单路径的长度。

高效双搜算法（Two-DFS Algorithm）：
1. 第一步 DFS：从树中任意选择一个起点节点 $x$，运行深度优先遍历找到距离 $x$ 最远的一个叶子节点 $y$。
2. 第二步 DFS：从这个最远端节点 $y$ 出发，运行第二次深度优先遍历，寻找到距离 $y$ 最远的一个节点 $z$。
3. 结论：从 $y$ 到 $z$ 的简单树上路径就是这棵树的最长直径！

演示速度：

选择演示模式并点击"开始演示"观摩树的拓扑性质推导。

🕸️ 树论性质动态生成拓扑图

// 1. 树的重心求解：最大子树极小化
int sz[MAXN], max_part[MAXN], centroid = 0;

void getCentroid(int u, int p) {
    sz[u] = 1;
    max_part[u] = 0;
    for (int v : g[u]) {
        if (v == p) continue;
        getCentroid(v, u);
        sz[u] += sz[v];
        max_part[u] = max(max_part[u], sz[v]); // 子节点子树最大值
    }
    // 上方父节点连通块大小 n - sz[u]
    max_part[u] = max(max_part[u], n - sz[u]); 
    if (centroid == 0 || max_part[u] < max_part[centroid]) {
        centroid = u; // 极小化重心
    }
}

// 2. 树的直径求解：双重 DFS 找最远叶子
int max_dist = 0, farthest = 0;

void dfs(int u, int p, int dist) {
    if (dist > max_dist) {
        max_dist = dist;
        farthest = u; // 更新当前最远叶子
    }
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u, dist + 1);
    }
}

void getDiameter() {
    max_dist = 0;
    dfs(1, 0, 0); // 第一次 DFS 从任意点 1 找最远端 y
    int y = farthest;
    
    max_dist = 0;
    dfs(y, 0, 0); // 第二次 DFS 从 y 找最远端 z
    // 此时从 y 到 z 的路径即为树的直径，max_dist 为直径长度
}

📋 树性推导演示历史步骤