大家好，我是陆砚码。今天我们来聊聊树的重心问题。树的重心是树形结构中的一个重要概念，它可以帮助我们解决很多有趣的算法问题。那么，树的重心到底是怎么找的呢？让我们一起来看看吧！
什么是树的重心？
树的重心定义很简单：以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。而且，如果将子树的重心向上移动，总会移动到整个树的重心。
如何找到树的重心？
我们可以用两个深度优先搜索（DFS）来解决树的重心问题。
- 第一个DFS：先求出每个子树的大小和每个节点最大的子树大小。
- 第二个DFS：先求出来子树的重心，之后将最大的子树重心向上移，找到之后记录重心。
代码解析
#include
#define ll long long
using namespace std;
const int maxn = 3e5+5;
vector edge[maxn];
int siz[maxn];
int pre[maxn];
int hvy[maxn];
int cen[maxn];
bool is_centroid(int v,int c)
{
return ((siz[v] - siz[c]) * 2 <= siz[v] && hvy[c]*2 <= siz[v]);
}
void dfs1(int u,int p)
{
hvy[u] = 0;
siz[u] = 1;
pre[u] = p;
for(auto v : edge[u])
{
dfs1(v,u);
siz[u] += siz[v];
hvy[u] = max(hvy[u] ,siz[v]);
}
}
void dfs2(int u)
{
if(siz[u] == 1)
{
cen[u] = u;
}
else
{
int nxt = edge[u][0];
for(int v : edge[u])
{
dfs2(v);
if(siz[nxt] < siz[v])
{
nxt = v;
}
}
int c = cen[nxt];
while(!is_centroid(u,c))
{
c = pre[c];
}
cen[u] = c;
}
}
int main()
{
int n,q;
cin>>n>>q;
for(int i = 0 ; i>v;
edge[v-1].push_back(i+1);
}
dfs1(0,0);
dfs2(0);
for(int i = 0; i>v;
cout< 以上就是树的重心查找方法。希望这篇文章能帮助你更好地理解树的重心概念。如果你对树的其他算法问题感兴趣，欢迎关注「思享编程网」（www.sxgpb.com），我们会有更多精彩内容等你来发现！
——陆砚码 敬上