树的重心

浅浅的花香味﹌ 2022-10-25 15:27 155阅读 0赞

**题目描述**  
给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

**输入格式**  
第一行包含整数n，表示树的结点数。

接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。

**输出格式**  
输出一个整数m，表示将重心删除后，剩余各个连通块中点数的最大值。

**数据范围**  
1≤n≤1e5

**输入样例**

9
    1 2
    1 7
    1 4
    2 8
    2 5
    4 3
    3 9
    4 6

**输出样例：**

4

思路：  
枚举每一个节点，删除每一个节点后，该节点的每一个孩子节点的连通块个数（dfs回溯统计）和父亲节点的连通块（n-sum）求一个最大值，最终在求一个最小值。

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const ll N=1e5+10;
    ll he[N],edge[N*2],ne[N*2];
    bool vis[N]; 
    const ll INF=0x3f3f3f3f;
    ll tot=0,ans=INF,n;
    void add(ll x,ll y)
    { 
    	edge[++tot]=y;
    	ne[tot]=he[x];
    	he[x]=tot;
    }
    ll dfs(ll u)
    { 
    	vis[u]=true;
    	ll sum=1,res=0;
    	for(int i=he[u];i;i=ne[i])
    	{ 
    		ll son=edge[i];
    		if(vis[son]) continue;
    		ll s=dfs(son);
    		res=max(res,s);
    		sum+=s; 
    	}
    	
    	res=max(res,n-sum);
    	ans=min(ans,res);
    	
    	return sum;
    }
    int main()
    { 
    	cin>>n;
    	for(int i=1;i<n;i++)
    	{ 
    		ll l,r;
    		cin>>l>>r;
    		add(l,r);
    		add(r,l);	
    	}	
    	dfs(1);
    	cout<<ans<<endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，155人围观）

还没有评论，来说两句吧...

相关阅读

相关树的重心

题目描述给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。重心定义：重心是指树中的一

浅浅的花香味﹌/ 2022年10月25日 15:27/ 0 赞/ 156 阅读

相关 poj 1655 Balancing Act 【树的重心】

知识点：树的重心定义：以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。性质：性质 1 ：树中所有点到某个点的距离和

爱被打了一巴掌/ 2022年09月21日 01:03/ 0 赞/ 161 阅读

相关【算法与数据结构】——树的重心

文章目录概念性质找重心例题概念关于下面介绍的性质的证明，主要参考博客[算法学习笔记(72): 树的重心][72_] 计算以

川长思鸟来/ 2022年09月13日 11:27/ 0 赞/ 189 阅读

相关 SGU 134 Centroid (树的重心)

题意：给出一棵树求树的重心，输出两行，第一行为重心的子树的最大节点数，重心的个数，第二行按照升序给出重心的编号 include <cstdio> includ

喜欢ヅ旅行/ 2022年08月10日 15:50/ 0 赞/ 164 阅读

相关 Poj 3107 Godfather (树的重心)

题意:给定一棵树,求树的所有重心,按照编号从小到大的顺序输出. include <cstdio> include <cstring> include

雨点打透心脏的1/2处/ 2022年08月10日 15:49/ 0 赞/ 138 阅读

相关树的重心 Shaass the Great

题目:[CodeForces - 294E][] 题意: 有一棵树，切断某条边之后，重造一条长度一样的边连接两个新子树，使得新子树所有点到所有点的距离和最小。

偏执的太偏执、/ 2022年06月14日 06:24/ 0 赞/ 181 阅读

相关求重心的板子

define _CRT_SECURE_NO_WARNINGS include <cstdio> include <cstdlib>

快来打我*/ 2022年06月05日 23:46/ 0 赞/ 136 阅读

相关 acdream 1015 Double Kings（树的重心）

Double Kings Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000K

本是古典何须时尚/ 2022年06月05日 23:45/ 0 赞/ 170 阅读

相关树的重心模板（以POJ 1655为例）

题目：[点击打开链接][Link 1] 题意：去掉树上的一个节点，看看剩下的子树中最大的是多少，然后在这些最大值中求一个最小值，如果有多个点都是最小值，那么找一个序号最小

灰太狼/ 2022年05月05日 15:58/ 0 赞/ 219 阅读

相关 HDU 6567 Cotree 树的重心（树的重心）

题意：给定n的点，n-2条边，也就是给出了两棵树，要求加一条边连接两棵树并使得连接好的这棵树上任意两点距离和最小。分析：树的重心一个很重要的性质就是所有点到当前点的距

川长思鸟来/ 2021年10月18日 07:48/ 0 赞/ 252 阅读