Poj 3107 Godfather (树的重心)

雨点打透心脏的1/2处 2022-08-10 15:49 165阅读 0赞

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

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N=50005;
    
    struct Edge
    {
    	int from,to,next;
    }edge[N<<1];
    
    int head[N],e,dp[N]; //所有子树中节点数的最大值,不含自身
    int n,son[N]; //以每个节点为根的子树的节点数,包含自身
    int ans[N];
    
    void Add (int u,int v)
    {
    	Edge E = {u, v, head[u]};
    	edge[e] = E;
    	head[u] = e++;
    }
    
    void DFS (int u, int pre)
    {
    	son[u]=1;
    	dp[u]=0;
    	for (int i=head[u]; ~i; i=edge[i].next)
    	{
    		int v=edge[i].to;
    		if (v==pre) continue;
    		DFS(v,u);
    		son[u]+=son[v];
    		dp[u]=max(dp[u],son[v]);
    	}
    	dp[u]=max(dp[u],n-son[u]);
    }
    
    int main ()
    {
    	while (~scanf("%d",&n))
    	{
    		memset(head,-1,sizeof(head));
    		e=0;
    		int i;
    		for (i=1;i<n;i++)
    		{
    			int u,v;
    			scanf("%d%d",&u,&v);
    			Add(u,v);
    			Add(v,u);
    		}
    		DFS(1,-1);
    		int minnum=N,cnt=0;
    		for (i=1;i<=n;i++)
    			if (minnum > dp[i])
    			{
    				cnt=0;
    				minnum=dp[i];
    				ans[cnt++]=i;
    			}
    			else if (minnum==dp[i])
    				ans[cnt++]=i;
    		for (i=0;i<cnt;i++)
    			printf(i==cnt-1?"%d\n":"%d ",ans[i]);
    	}
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关树的重心专题

解题思路：选择一个节点作为根，设dp\[i\]表示以i为根的树的总节点个数，dp\[i\]=满足j为其子节点的的d\[j\]之和再加1（根节点）。只需在dfs过程中找到最大的子

清疚/ 2023年08月17日 16:26/ 0 赞/ 127 阅读

相关树的重心

树的重心 > 说明：下面的定义等都是按照个人的理解所表述的，如有错误欢迎批评指出。 1.定义：去掉该节点，最大的连通块（子树）的节点数目最少，则该节点点称作该树

红太狼/ 2023年07月10日 08:22/ 0 赞/ 19 阅读

相关树直径和树重心

主要是留个板子因为我似乎不会证明树直径丛树的任一点开始找一个离该节点最远的点，该点必为树直径的一端点，再从该点出发找最远点即为树直径方法：dfs 时间O(2n)

冷不防/ 2023年06月12日 04:24/ 0 赞/ 19 阅读

相关树的重心

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

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

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

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

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

相关 Poj 3107 Godfather (树的重心)

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

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

相关【树形dp+前向星】Godfather POJ - 3107

Think: 1题意：给出一棵树，询问试探删除一个结点后可使得余下两个连通子图中的最大结点子图的结点数量是所有结点试探的最小值（找到一个点,其所有的子树中最大的子树节点数最

分手后的思念是犯贱/ 2022年06月14日 10:17/ 0 赞/ 205 阅读

相关树的重心 Shaass the Great

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

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

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

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

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

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

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

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