给定一颗树,树中包含n个结点(编号1~n)和n-1条无向边。
请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
输入格式
第一行包含整数n,表示树的结点数。
接下来n-1行,每行包含两个整数a和b,表示点a和点b之间存在一条边。
输出格式
输出一个整数m,表示将重心删除后,剩余各个连通块中点数的最大值。
数据范围
1≤n≤105
输入样例
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;
typedef long long ll;
const ll N=2e5+10;
ll e[N],ne[N],h[N],st[N],idx,n;
ll ans=0x3f3f3f3f; // ans是最小的最大值初始化为正无穷;
void add(ll a,ll b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
/*
数的深搜模板;
ll dfs(ll u)
{
st[u]=1;
for(ll i=h[u];i!=-1;i=ne[i])
{
j=e[i];
if(!st[j])
{
dfs(j);
}
}
}
*/
ll dfs(ll u)
{
ll res=0; //res为去掉u之后得到的联通块中点数的最大值
ll sum=1; //sum是u和以u未父节点的分支的点数的总值;
st[u]=1; //u点已经被遍历过;
for(ll i=h[u];i!=-1;i=ne[i])
{
ll j=e[i];
if(!st[j])
{
ll s=dfs(j); //dfs返回的是j和以j为父节点的分支的点数的总值
res=max(res,s);//更新res
sum+=s;
}
}
res=max(res,n-sum); //更新其他
ans=min(ans,res); //更新去除u后剩余各连通块中剩余点数目的最大值的最小值;
return sum;
}
int main()
{
memset(h,-1,sizeof(h)); //记得初始化;
cin>>n;
for(ll i=0;i<n-1;i++)
{
ll a,b;
cin>>a>>b;
add(a,b);add(b,a);
}
df(1); //从任一节点开始搜索;
cout<<ans<<endl;
}
佬佬,为什么4到不了1要用n - sum表示呀这不是一个无向图吗,4-1之间是有边的呀
sum以u为根的树的节点数,那个图u是4号节点,去掉u后的联通块分为两部分,一部分是以u为根节点的树,一部分是u的上面一部分,n-sum表示的是上面一部分联通块的节点数
为什么上面的那一部分不可以看成以u为根节点的子树
因为u上面的节点已经被遍历过了st数组标记了不会回溯了