[Note] 直径与重心

[L4] 直径与重心

1. 生态位

• 识别:

  1. 最远/最长: 寻找树上任意两点间的最长简单路径（直径）。

  2. 平衡/分割: 寻找一个点，删除它后使得剩余的最大连通块节点数最小（重心）。

  3. 偏心距: 寻找一个点，使得它到树上最远点的距离最小（树的中心/半径）。

• 地位: 树的基本物理属性。

  • 直径定义了树的“跨度”极限。

  • 重心定义了树的“平衡”极限。

• 用途:

  • 直径: 解决巡逻路径、最远点对查询、树网的核。

  • 重心: 点分治 的前置核心，用于保证分治层数为 $O(\log N)$。

2. 逻辑支点

2.1 树的直径

• 核心性质：从树上任意一点 $u$ 出发，能走到的最远节点 $v$，一定是直径的一个端点。

• 中心性质：树的几何中心（到最远点距离最小的点）一定位于直径的中点（或中点旁）。

• 求解策略:

  1. 两次 DFS/BFS: 适用于非负权边。方便求出具体路径。

     • 第一次从任意点 $x$ 找到最远点 $u$（直径一端）。
     • 第二次从 $u$ 找到最远点 $v$（直径另一端）。

  2. 树形 DP: 适用于含负权边。

     • 维护 $d_1[u]$ (最长链) 和 $d_2[u]$ (次长链)，且两条链不来自同一个子树。
     • $Ans = \max(d_1[u] + d_2[u])$。

2.2 树的重心

• 核心定义: 删除该点后，最大子树的大小 $\le \frac{N}{2}$。

• 物理性质:

  1. 一棵树最多有两个重心，且这两个重心一定相邻。

  2. 树上所有点到重心的距离和最小。

  3. 把两棵树通过一条边连起来，新的重心在原两棵树重心的连线上。

• 单调移动：若删边则向重儿子移动

  • 无权树: 如果向邻居 $v$ 移动，当且仅当 $sz[v] > \frac{N}{2}$ 时，重心在 $v$ 的子树中。

  • 带权树: 设总权值为 $S$，若邻居 $v$ 的子树权值和 $sz\_w[v] \times 2 > S$，则加权重心一定在 $v$ 的方向。

3. 实战部署

3.1 直径：两次 DFS 法 (求路径/端点)

▶

直径 (2-DFS)

int dist[maxn], fa[maxn]; // fa 用于记录路径
int ed;

void dfs_dist( int u, int p, int d )
{
    dist[u] = d;
    fa[u] = p;
    if( d > dist[ed] ) ed = u;
    
    for( auto& [v, w] : adj[u] )
    {
        if( v != p ) dfs_dist( v, u, d + w );
    }
}

int get_diameter_dfs()
{
    // 1. 第一遍，从任意点 (如 1) 出发找端点 u
    ed = 0; dist[0] = -1;
    dfs_dist( 1, 0, 0 );
    int u = ed;

    // 2. 第二遍，从 u 找端点 v
    ed = 0; dist[0] = -1;
    dfs_dist( u, 0, 0 );
    int v = ed;

    // 此时 dist[v] 即为直径长度，u 到 v 即为最长路径，可通过 fa 数组回溯
    return dist[v];
}

3.2 直径：树形 DP 法 (通用/负权)

▶

直径 (Tree DP)

int d1[maxn], d2[maxn]; // d1: 最长链，d2: 次长链
int ans_dp = 0;

void dfs_dp( int u, int p )
{
    d1[u] = d2[u] = 0;
    for( auto &[v, w] : adj[u] )
    {
        if( v == p ) continue;
        
        dfs_dp( v, u );
        
        int t = d1[v] + w; 
        if( t > d1[u] ) d2[u] = d1[u], d1[u] = t;
        else if( t > d2[u] ) d2[u] = t;
    }
    ans_dp = max( ans_dp, d1[u] + d2[u] );
}

int get_diameter_dp( )
{
    ans_dp = 0;
    dfs_dp( 1, 0 );
    return ans_dp;
}

3.3 重心：DFS 求解

▶

重心

int sz[maxn];       // 子树大小
int f[maxn];        // 删除 u 后，最大连通块的大小
int root;           // 重心
int n;              // 总点数

void get_root( int u, int p )
{
    sz[u] = 1;
	f[u] = 0;
    
    for( auto v : adj[u] )
    {
        if( v == p ) continue;
        get_root( v, u );
        sz[u] += sz[v];
        
		// 更新最大子树
        f[u] = max( f[u], sz[v] );
    }
    
    // 考虑上方连通块 ( n - sz[u] )
    f[u] = max( f[u], n - sz[u] );
    
    // 更新全局重心：这就体现了"最大值最小"的思想
	if( f[u] < f[root] ) root = u;
}

f[0] = n + 1;
root = 0;

4. 知识关联

• 关联笔记:

  • [[树形DP体系]]: 直径的 DP 写法本质就是树形 DP 的入门题。

  • [[点分治]]: 重心是点分治算法保证时间复杂度的核心（每次分割规模减半）。

• 实战案例 (直径体系):

  • 骨架构造: CF911F Tree Destruction (利用直径端点距离最大进行贪心删点)。

  • 几何中心: P5536 核心城市 (直径中点为根，长链剖分贪心)。

  • 偏心距: P1099 树网的核 (直径上的双指针与分支最值)。

  • 负权直径: P3629 巡逻 (环路边权取反，DP 求第二次直径)。

• 实战案例 (重心体系):

  • 性质定义: P1395 会议 (距离和最小点)。

  • 结构调整: CF1406C Link Cut Centroids (双重心化单重心的构造)。

  • 动态/带权: P5666 树的重心 / P2726 树的双中心 (利用倍增在重链上寻找重心分割点)。