20251122树的直径、重心、中心
引入
树是一种特殊的图，因其看起来像一颗倒挂的树而得名。
树的定义为：n nn个点n − 1 n-1n−1条边的无向连通图。
树的直径
定义树上任意两点之间最长的简单路径为树的直径，一棵树可能有很多直径，如菊花图等。
DFS求法
在没有负边权的情况下，我们一般使用两次DFS求树的直径：
- 第一次DFS从任意位置出发，找到距离起点最远的点x ， x x，xx，x是一条直径的端点之一；
- 第二次DFS从点x xx出发，找到距离点x xx最远的点y yy，x xx到y yy的路径即为一条直径。
树形DP
当图中存在负边权时，无法使用DFS算法求解最长路径。此时应采用树形DP方法：首先选取任意节点作为根节点，对于每个节点x xx，计算其子树中以x xx为顶点的最长路径。该路径长度等于x xx向下的最长路径与次长路径之和。在DFS遍历过程中，只需维护这两个路径长度信息即可完成计算。
实现
voiddfs(intu,intfa){d1[u]=d2[u]=0;//d1是最长路，d2是次长路for(intv:E[u]){if(v==fa)continue;dfs(v,u);intdv=d1[v]+1;if(dv>d1[u]){d2[u]=d1[u];d1[u]=dv;}elseif(dv>d2[u]){d2[u]=dv;}}ans=max(ans,d1[u]+d2[u]);}树的重心
要确定树的重心，需选择一个根节点使其子树分布尽可能均匀。这里用最大子树的节点数来衡量均匀程度——该数值越小，分布越均匀。因此，使最大子树节点数最小的根节点即为树的重心。
性质
- 树的重心最多只有两个，若有两个一定相邻。
- 以重心作为根节点，根节点的最大子树节点数不会超过n / 2 n/2n/2
- 树上所有点到某个点的距离之和中，到重心的最小。
- 把两棵树用一条边连起来，形成的新的树的重心在原来两树重心之间的路径上。
- 在一颗树上添加一个叶子节点，重心最多向叶子节点移动一条边。
求法
以任意节点为根进行DFS遍历，可以计算每个节点的子树规模。具体而言：
- 向下递归时统计各子树节点数
- 向上部分的大小可通过公式n-size[cur]求得
实现
voiddfs(intx,intfa){for(intv:E[x]){if(v==fa)continue;dfs(v,x);sz[x]+=sz[v];mx[x]=max(mx[x],sz[v]);//向下子树大小}sz[x]++;mx[x]=max(mx[x],n-sz[x]);//向上子树大小}树的中心
树的中心指的是树中某个特殊节点，当以其为根时，能使得从该节点出发的最长路径长度达到最小。它具有以下关键特性：
- 树的中心数量不超过两个，且若存在两个中心则必定相邻
- 中心必然位于树的直径路径上
- 中心到任意节点的距离不超过树直径的一半
- 所有节点到其最远点的路径必然经过中心
求解步骤：
- 计算最长路径：采用深度优先搜索(DFS)算法，为每个节点计算其作为根时的最长路径和次长路径
- 计算外部路径：通过换根动态规划技术，计算每个节点在其子树之外的最长路径
- 确定中心节点：对每个节点求取其最长路径与外部路径的最大值，其中最小值对应的节点即为树的中心
#include<bits/stdc++.h>usingnamespacestd;vector<int>E[100005];intn,dp1[100005],dp2[100005],p1[100005],p2[100005],up[100005];voiddfs(intx,intfa){for(inti=0;i<E[x].size();i++){intv=E[x][i];if(v==fa)continue;dfs(v,x);ints=dp1[v]+1;if(s>dp1[x]){dp2[x]=dp1[x];dp1[x]=s;p2[x]=p1[x];p1[x]=v;}elseif(s>dp2[x]){dp2[x]=s;p2[x]=v;}}}voiddfs1(intx,intfa){for(inti=0;i<E[x].size();i++){intv=E[x][i];if(v==fa)continue;if(v==p1[x]){up[v]=max(dp2[x],up[x])+1;}else{up[v]=max(dp1[x],up[x])+1;}dfs1(v,x);}}intmain(){cin>>n;for(inti=1;i<n;i++){intu,v;cin>>u>>v;E[u].push_back(v);E[v].push_back(u);}dfs(1,0);dfs1(1,0);intmn=INT_MAX;for(inti=1;i<=n;i++){mn=min(mn,max(dp1[i],up[i]));}for(inti=1;i<=n;i++){if(max(dp1[i],up[i])==mn){cout<<i<<" ";}}return0;}