总结：树的中心

· · 算法·理论

（注：本文为作者的真实学习情况，没有借鉴与抄袭他人的内容，制作不易，点个赞支持一下吧）。

\texttt{总结：树的中心}

\texttt{前置知识：}树的直径

  • 树的直径的性质

  1. 假设边权非负，那么树的直径的端点则一定在度为 1 的点上。

  2. 如果边权取任意值（也就是说可为负数），那么任意一点到达直径上的一点的距离一定最短。

Code（使用的是树形 DP 求取的树的直径）。

树形 DP 求取树的直径的优势是可以直接处理所有的边权，但是缺点是端点不易获取。

树的中心定义：在一棵树中（无根树），如果将节点 x 作为根节点时，从 x 出发的最长链最短，那么就将点 x 称为这棵树的中心。

推导出性质：将刚好把直径一分为 2 时，此时则可以保证，以此时的中心点为根时，则最长链最小。

  1. 树的中心不一定唯一，但最多有 2 个，且这两个中心是相邻的。

  2. 树的中心一定位于树的直径上。

  3. 树上所有点到其最远点的路径一定交会于树的中心。

  4. 当树的中心为根节点时，其到达直径端点的两条链分别为最长链和次长链。

  5. 当通过在两棵树间连一条边以合并为一棵树时，连接两棵树的中心可以使新树的直径最小。

  6. 树的中心到其他任意节点的距离不超过树直径的一半。

推广性质：所有的直径都相交于树的中心。

此处给出两种树的中心的求法。

  1. 使用 dfs 求解，由于是无根树，直接枚举根节点，然后使用 dfs 直接求取树的直径，时间复杂度为 O(n\log n)。

  2. 使用树形 DP（换根 DP） 算法求解。

由于使用 dfs 算法十分简单，故只给出换根 DP 的详细做法：

寻找一个点 x，使其作为根节点时，最长链的长度是最短的，则称 x 为树的中心。

\texttt{具体步骤}

  1. 维护数组 down1_x，表示以 x 作为子树的根节点时的最长链的长度。

简化意思：记录点 x 往下的最大链。

  1. 维护数组 down2_x，表示

简化意思：记录点 x 往下的次大链，（不能与 down1_x 重叠）。

  1. 维护数组 up_x，表示节点 x 的子树外的最长链，此处有一性质：即该链必将经过 x 的父亲节点。

  2. 那么最终的点 x 如果使得 \max(down1_x,_up_x) 最小，那么 x 即为树的中心。

\texttt{实现步骤}：

  1. 利用树的中心的性质，直接找到每个点的最长链的最小值。

但是，此处出现了一个问题，就是维护的 up_x 每一次求解都需要提出来一个根节点，这样的时间复杂度无法接受。

  1. 求解所有的 down1_x 与 down2_x，直接使用这两个数组来直接求取 up_x，即可避免提根的时间复杂度。

  2. 只需要求解所有的 up_x 即可得到答案。

故现在使用换根 DP 的基本思路已经说完，开始使用代码实现上面的思路。

补充（换根 DP 的基本步骤）

步骤 1：任意选取一个根节点。

步骤 2：dfs 的过程之中，统计出当前子树内的节点对当前节点的贡献。

步骤 3：再来一次 dfs，统计出当前节点的父节点对当前节点的贡献，然后合并统计答案。

Code。（换根 DP）

综上所述，使用换根 DP 做法的时间复杂度为 O(n)。

\texttt{例题讲解}

\texttt{U392706【模板】树的中心}

题目描述：

给定一棵 n 个节点的树，求树的所有中心。

思路：

本题为树的中心模板题，直接使用树的中心（换根 DP）做法直接求取即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,down1[N],down2[N],up[N],pre[N];
struct node
{
    int v;
    int w;
};
vector<node>G[N];
void dfs1(int u,int fa)
{
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i].v,w=G[u][i].w;
        if(v!=fa)
        {
            dfs1(v,u);
            int x=down1[v]+w;
            if(down1[u]<x)down2[u]=down1[u],down1[u]=x,pre[u]=v;
            else if(down2[u]<x)down2[u]=x;
        }
    }
}
void dfs2(int u,int fa)
{
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i].v,w=G[u][i].w;
        if(v!=fa)
        {
            if(pre[u]==v)up[v]=max(down2[u],up[u])+w;
            else up[v]=max(down1[u],up[u])+w;
            dfs2(v,u);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    dfs1(1,0);
    dfs2(1,0);
    int res=1e9;
    for(int i=1;i<=n;i++)res=min(res,max(down1[i],up[i]));
    for(int i=1;i<=n;i++)if(res==max(down1[i],up[i]))cout<<i<<'\n'; 
    return 0;
}