树的重心
2026-03-15 11:05:04
发布于：浙江
3阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int size[N],maxpart[N];
vector<int> adj[N];
int ans=N,n;
void dfs(int u,int p){
size[u]=1;maxpart[u]=0;
for(int v:adj[u]){
if(v==p) continue;
dfs(v,u);
size[u]+=size[v];
maxpart[u]=max(maxpart[u],size[v]);
}
maxpart[u]=max(maxpart[u],n-size[u]);
ans=min(ans,maxpart[u]);
}
int main(){
cin>>n;
for(int i=1;i<n;++i){
int a,b;cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1,0);
cout<<ans;
return 0;
}
这里空空如也
有帮助，赞一个