【模板树的重心】小G有一个大树

爱被打了一巴掌 2024-03-22 17:33 53阅读 0赞

[A-小G有一个大树\_牛客竞赛动态规划专题班树型dp例题 (nowcoder.com)][A-_G_dp_ _nowcoder.com]

以下是关于树的重心的一些性质：

![e5cbbbb227714fd48d789ae58c6aefd3.png][]

题意：

![f555ee40d76f4937ac84b4dd01bf0b98.png][]

思路：

用树形DP求出每个结点的最大子树，统计每个结点最大子树的最小值

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e3+10,mxe=1e3+10,mnf=0x3f3f3f3f;
    struct ty{
    	int to,next,vis;
    }edge[mxe<<1];
    int n,u,v,tot=0,ans=mnf,ansi;
    int head[mxn],sz[mxn],dp[mxn];
    void add(int u,int v){
    	edge[tot].vis=0;
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void init(){
    	tot=0;ans=mnf;
    	for(int i=0;i<=n;i++){
    		head[i]=-1;
    		sz[i]=dp[i]=0;
    	}
    }
    void dfs(int u){
    	sz[u]=1;
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].vis) continue;
    		edge[i].vis=1;edge[i^1].vis=1;
    		dfs(edge[i].to);
    		sz[u]+=sz[edge[i].to];
    		dp[u]=max(dp[u],sz[edge[i].to]);
    	}
    	dp[u]=max(dp[u],n-sz[u]);
    	ans=min(ans,dp[u]);
    }
    int main(){
    	while(scanf("%d",&n)==1){
    		init();
    		for(int i=1;i<=n-1;i++){
    			scanf("%d%d",&u,&v);
    			add(u,v);add(v,u);
    		}
    		dfs(1);
    		for(int i=1;i<=n;i++){
    			if(dp[i]==ans) ansi=i;
    		}
    		printf("%d %d\n",ansi,dp[ansi]);
    	}
    	return 0;
    }

[A-_G_dp_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/28258/A
[e5cbbbb227714fd48d789ae58c6aefd3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/4be529d8bd9f4d1f9e087318ee7b8aa1.png
[f555ee40d76f4937ac84b4dd01bf0b98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/e7da1d530b794092b6fd57869f186f93.png

发表评论取消回复

表情：

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

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

相关阅读

相关【模板树的重心】小G有一个大树

[A-小G有一个大树\_牛客竞赛动态规划专题班树型dp例题 (nowcoder.com)][A-_G_dp_ _nowcoder.com] 以下是关于树的重心的一些性质：

爱被打了一巴掌/ 2024年03月22日 17:33/ 0 赞/ 54 阅读

相关树的重心专题

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

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

相关树直径和树重心

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

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

相关树的重心

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

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

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

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

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

相关 SGU 134 Centroid (树的重心)

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

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

相关 Poj 3107 Godfather (树的重心)

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

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

相关树的重心 Shaass the Great

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

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

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

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

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

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

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

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