题意
- 对于一棵树,我们希望找到一个点,使得删除这个点之后,最大子树的结点数最小
- 以边的形式输入,输出被删除的点的编号和删除后最大子树的结点数
思路
- 考虑用无根树描述,对于树的某一个结点,删掉后,整棵树变为两部分
- 故另
表示删除这个点后最大子树结点数,
表示这个点除了父亲以外的子树的总结点数,则
就是祖先部分的结点数
- 得到
,u是i的每一个儿子,%2B1&preview=true)
- 所求答案为所有
中最小的一个
代码
#include<bits/stdc++.h>
#define maxn 1024
using namespace std;
int n;
int tol[maxn],f[maxn];
vector<int> tree[maxn];
void dfs(int x,int fa){
int tolu=-0x3f3f3f3f;
tol[x]=1;
for(int i=0;i<tree[x].size();i++){
int son=tree[x][i];
if(son==fa) continue;
dfs(son,x);
tol[x]+=tol[son];
tolu=max(tolu,tol[son]);
}
f[x]=max(n-tol[x],tolu);
// cout << x << ' ' << fa << ' ' << tolu << ' ' << tol[x] << endl ;
}
int main(){
while(cin >> n){
for(int i=0;i<maxn;i++){
tree[i].clear();
}
for(int i=1;i<n;i++){
int a,b;
cin >> a >> b ;
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs(1,0);
int idx=0,ans=0x3f3f3f3f;
for(int i=1;i<=n;i++){
if(f[i]<ans){
idx=i;
ans=f[i];
}
}
cout << idx << ' ' << ans << endl ;
}
return 0;
}