树的属性

直径

定义

树上最长的两点间简单路径

性质

• 一棵树可以有多条直径
• 任意节点，取距离其最远的点，一定是直径的一端

求解

• 一次 dfs 找到直径一端
• 再次 dfs 找到另一端

int s; // 端点
vector<int> d; // 到端点距离
int dfs(int u, int p){
    // 遍历出边
    for(int v: adj[u]){
        // 跳过回头路
        if(v == p) continue;
        // 更新距离和端点
        d[v] = d[u] + 1;
        if(d[v] > d[s]) s = v;
        dfs(v, u);
    }
}
// 第一次找到直径一端
s = 0;
dfs(0, -1);
// 第二次找到直径另一端
d[s] = 0;
dfs(s, -1);
// 直径长度
ans = d[s];

重心

定义

最大子树最小的节点

性质

• 删去重心，得到的所有子树大小 $\leq \dfrac{n}{2}$

求解

• dfs 找出每个子节点子树大小
• 总节点数 $-$ 子树大小 $=$ 父节点子树大小（不含本子树）

// 总结点数、重心和对应子树大小
int n, core = 0, coreSize = 1e9;
// 所有子树大小
vector<int> size;
// 邻接表
vector<vector<int> > adj;
void dfs(int u, int fa){
    // 记录当前节点最大子树
    int maxSize = 0;
    // 初始化当前节点子树大小
    size[u] = 1;
    // 遍历出边
    for(int v: adj[u]){
        // 跳过父节点
        if(v == fa) continue;
        // 递归更新子节点
        dfs(v, u);
        // 更新当前节点树大小和最大子树
        size[u] += size[v];
        maxSize = max(maxSize, size[v]);
    }
    // 再与父节点的另一边子树比较
    maxSize = max(maxSize, n - size[u]);
    // 看看是不是重心（最大子树更小）
    if(maxSize < coreSize)
        core = u, coreSize = maxSize;
}