输入样例:
9 1 2 1 7 1 4 2 8 2 5 4 3 3 9 4 6
期望输出:
4
代码实现:
#include<bits/stdc++.h> using namespace std;const int N =1e5+10 , M=2*N;int n,m; int h[N],e[M],ne[M],idx; bool vis[N]; int ans=N ;void add(int a,int b)//插入一条a指向b的边 {e[idx]=b;ne[idx]=h[a];h[a]=idx++; }int dfs(int u)//u代表的是第几个点 {vis[u]=1;int sum = 1,res =0; //sum 为当前子树的大小,res为把这一点删除后的连通块的最大值for(int i=h[u];i!=-1;i=ne[i]){int k=e[i];if(!vis[k]){int s = dfs(k); //当前子树的大小res = max(res,s);//看看所有子树哪个更大sum +=s;//求自己为父节点树的大小}}res = max(res,n-sum); //看看删除这个点的其他部分与最大子树哪个大ans = min(ans,res);//找到最小的答案return sum; }int main() {cin>>n;memset(h,-1,sizeof(h));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; }