此题解仅供自己参考
算法1
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
const int M=N*2;
int e[M],ne[M],h[N],idx;
int ans=N,n;
bool st[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int dfs(int u)
{int size=0;//size是存放联通块中点数的最大值 ans是所有最大值中的最小值
st[u]=true;
int num=1;//num代表这以当前节点为根节点时,该条枝干上的点的个数
for(int i=h[u];i!=-1;i=ne[i])
{
if(!st[e[i]]){
int s=dfs(e[i]);
size=max(size,s);//求此为根节点的不同枝干中 点数的最大值
num+=s;//
}
} size=max(size,n-num);//判断最大子连通块与父连通块的最大值
ans=min(size,ans);
return num;
}
int main()
{ cin.tie(0);
ios::sync_with_stdio(0);
memset(h,-1,sizeof h); //初始化h[]表 -1表示空
cin>>n;
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(1);
cout<<ans<<endl;
return 0;
}