题目描述
用vector存储
样例
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=100010;
vector<int> p[N];
int f[N];
int n;
int ans=N;
int dfs(int u,int father,int tr){
int size=0,sum=0;
if(u==tr)return size;
for(auto &node:p[u]){
int s=dfs(node,u,father);
size=max(size,s);
sum+=s;
}
size=max(size,n-sum-1);
ans=min(ans,size);
return sum+1;
}
int main(){
cin>>n;
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
p[a].push_back(b);
p[b].push_back(a);
}
//求权值
dfs(1,0,0);
cout<<ans<<endl;
return 0;
}