树的直径

概念

树的直径：树上相距最远的两个点的距离。

树的中心：若树上的点 $x$ 作为根结点时，树的高度最小，那么 $x$ 为树的中心。

树的中心不一定有一个，且树的中心一定在树的直径上。

性质

1.树的直径不一定唯一；

2.若树的直径有多条，那么所有的直径会交与一点；

3.树上任意一点距其最远的点一定是树的直径的一个端点；

4.若树 A 的直径的两个端点为 $x_1,y_1$，树 B 的直径的两个端点为 $x_2,y_2$，那么树 A 和树 B 任取一个端点连边合并后，新的直径的端点一定是 $x_1,x_2,y_1,y_2$ 中的两个。

树的重心

定义

对于一颗树形结构，若结点 $x$ 作为根结点时，其最大的子树大小不超过 $\left\lfloor\dfrac{n}{2}\right\rfloor$，则结点 $x$ 称为树的重心。

性质

1.树上结点到 $x$ 的距离和一定是最小的；

2.树的中心至多两个，且一定相邻；

3.若树删除一个叶子结点，则重心最多偏移一位；

4.若两棵树的重心为 $x,y$，那么任意在两棵树之间连边，新的重心一定在 $x\to y$ 的路径上。

实现

核心代码：

void dfs1(int x, int fa){
  sz[x]++;
  for (auto v : a[x]){
    if (v != fa){
      dfs1(v, x);
      sz[x] += sz[v];
      dis[x] = max(dis[x], sz[v]);
    }
  }
  dis[x] = max(dis[x], n - sz[x]);
  if (dis[x] <= n / 2){
    p = x;
  }
}

树的中心

概念

在一棵树中，如果当 $x$ 为根结点时，整棵树的高度最小，则称 $x$ 为树的中心。

注意到，树的中心可能不唯一，但最多两个。

性质

1.树的中心一定在树的直径上。

2.树的中心为根结点时，根结点到树的直径的 $2$ 个端点的路径分别为树的最长链和树的次长链。

3.树上所有结点到最远段的路径交于树的中心。

4.树的直径如果有多条，那么所有直径交于树的中心。

实现

设 $len1_x$ 表示以点 $x$ 为根结点时其子树最长链的长度，$len2_x$ 表示以点 $x$ 为根结点时其子树次长链的长度，$up_x$ 表示点 $x$ 往上经过 $fa_x$ 的最长链。

那么，点 $x$ 为根节点时，树的高度 $h_x=\max(len1_x, up_x)$。

然后选取 $h_x$ 最小的即可。

伪代码：

dfs(x, fa):
  for x -> v:
    if(v != fa):
      dfs(v, x)
      if (len1[v] + w > len1[x]):
        len2[x] = len1[x]
        len1[x] = len1[v] + w
      else:
        len2[x] = max(len2[x], len1[v] + w)
      up[v] = up[x] + w
      if (len1[x] == len1[v] + w):
        up[v] = max(up[v], len2[x] + w)
      else:
        up[v] = max(up[v], len1[x] + w)