专栏文章

总结：树的中心

CCartis
算法·理论参与者 7已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@miq3h8lp
此快照首次捕获于
2025/12/03 22:20
3 个月前
此快照最后确认于
2025/12/03 22:20
3 个月前
查看原文
（注：本文为作者的真实学习情况，没有借鉴与抄袭他人的内容，制作不易，点个赞支持一下吧）。

总结：树的中心\texttt{总结：树的中心}

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

  • 树的直径的性质
  1. 假设边权非负，那么树的直径的端点则一定在度为 11 的点上。
  2. 如果边权取任意值（也就是说可为负数），那么任意一点到达直径上的一点的距离一定最短。
Code（使用的是树形 DP 求取的树的直径）。
树形 DP 求取树的直径的优势是可以直接处理所有的边权，但是缺点是端点不易获取。

  • 定义\texttt{定义}

树的中心定义：在一棵树中（无根树），如果将节点 xx 作为根节点时，从 xx 出发的最长链最短，那么就将点 xx 称为这棵树的中心。
推导出性质：将刚好把直径一分为 22 时，此时则可以保证，以此时的中心点为根时，则最长链最小。

  • 性质\texttt{性质}

  1. 树的中心不一定唯一，但最多有 22 个，且这两个中心是相邻的。
  2. 树的中心一定位于树的直径上。
  3. 树上所有点到其最远点的路径一定交会于树的中心。
  4. 当树的中心为根节点时，其到达直径端点的两条链分别为最长链和次长链。
  5. 当通过在两棵树间连一条边以合并为一棵树时，连接两棵树的中心可以使新树的直径最小。
  6. 树的中心到其他任意节点的距离不超过树直径的一半。
推广性质：所有的直径都相交于树的中心。

  • 求法\texttt{求法}

此处给出两种树的中心的求法。
  1. 使用 dfs 求解，由于是无根树，直接枚举根节点，然后使用 dfs 直接求取树的直径，时间复杂度为 O(nlog⁡n)O(n\log n)。
  2. 使用树形 DP（换根 DP） 算法求解。
由于使用 dfs 算法十分简单，故只给出换根 DP 的详细做法：
寻找一个点 xx，使其作为根节点时，最长链的长度是最短的，则称 xx 为树的中心。

具体步骤\texttt{具体步骤}

  1. 维护数组 down1xdown1_x，表示以 xx 作为子树的根节点时的最长链的长度。
简化意思：记录点 xx 往下的最大链。
  1. 维护数组 down2xdown2_x，表示
简化意思：记录点 xx 往下的次大链，（不能与 down1xdown1_x 重叠）。
  1. 维护数组 upxup_x，表示节点 xx 的子树外的最长链，此处有一性质：即该链必将经过 xx 的父亲节点。
  2. 那么最终的点 xx 如果使得 max⁡(down1x,upx)\max(down1_x,_up_x) 最小，那么 xx 即为树的中心。

实现步骤\texttt{实现步骤}：

  1. 利用树的中心的性质，直接找到每个点的最长链的最小值。
但是，此处出现了一个问题，就是维护的 upxup_x 每一次求解都需要提出来一个根节点，这样的时间复杂度无法接受。
  1. 求解所有的 down1xdown1_x 与 down2xdown2_x，直接使用这两个数组来直接求取 upxup_x，即可避免提根的时间复杂度。
  2. 只需要求解所有的 upxup_x 即可得到答案。
故现在使用换根 DP 的基本思路已经说完，开始使用代码实现上面的思路。

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

步骤 1：任意选取一个根节点。
步骤 2：dfs 的过程之中，统计出当前子树内的节点对当前节点的贡献。
步骤 3：再来一次 dfs，统计出当前节点的父节点对当前节点的贡献，然后合并统计答案。
Code。（换根 DP）
综上所述，使用换根 DP 做法的时间复杂度为 O(n)O(n)。

例题讲解\texttt{例题讲解}

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

题目描述：

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

思路：

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

代码：

CPP
#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;
}

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...