二叉树的重心与直径

· · 算法·理论

前言

爬

掉绿名了呜呜呜 复习pj知识ing

树的直径

先上定义

树上任意两节点之间最长的简单路径即为树的「直径」

也是自己口胡了算法 原理其实很简单

首先用感性思考一下

先从任意节点（通常是根）遍历一遍

找到距离该点最远的节点

然后再从找到的点出发

再次找到距离该点最远的节点

这条路径就是树的直径

ps：这个方法不能用于有负权边的树

或者可以用树dp，但是只能求出直径长度

但是窝补灰啊

咳咳，简单证明一下dfs

定理：在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。

有了这个就能癔症易证了

定理用反证法可证

代码实现如下。

constexpr int N = 10000 + 10;

int n, c, d[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  d[c] = 0, dfs(c, 0);
  printf("%d\n", d[c]);
  return 0;
}

over

树的重心

无根树的重心定义为：令 x 为树根，有 y 与 x 相邻，使得 y 的子树大小的最大值最小，这样的 x 即树的「重心」。

重心有 1 个 或 2 个，若有 2 个则这 2 个重心相邻

求法也比较简单

这里口胡一下

首先要用到一个性质

即以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。

那么利用这个性质

我们很容易想到去检查每个子树

即对于这课无根树，选择一个节点作为根，求出每个节点为根子树的大小。

然后枚举每一个结点

枚举时检查它往下的子树（即以它的每个儿子为根的子树）与往上的子树（即整棵树去除以其为根的子树的部分）的大小是否都小于等于 n/2 。

即可求得

代码

int size[N]，fa[N];  
//size[i] 表示以i为根的子树节点个数
int getsize(int u) //求u为根各个子树的大小 {
    size[u]=1;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v==fa[u])continue;
        fa[v]=u;   //找到v的父亲u 
        size[u]+=getsize(v); 
     } 
    return size[u];
} 
bool check(int u)   //检测 u 是否为树的根 {
    if(n-size[u]>n/2)return 0;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v==fa[u])continue; 
        if(size[v]>n/2) return 0;
    }
    return 1;
}