CSP复习每日一题(四)
树的重心
给定一颗树,树中包含 n n n 个结点(编号 1 ∼ n 1∼n 1∼n)和 n − 1 n−1 n−1条无向边。请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义: 重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
输入格式
第一行包含整数 n n n,表示树的结点数。
接下来 n − 1 n−1 n−1 行,每行包含两个整数 a a a 和 b b b,表示点 a a a 和点 b b b 之间存在一条边。
输出格式
输出一个整数 m m m,表示将重心删除后,剩余各个连通块中点数的最大值。
数据范围
1 ≤ n ≤ 105 1≤n≤105 1≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例
4
思路
- 基本框架: D F S DFS DFS
- 判断一个结点是否是重心的方法:
-
假设当前按照深度优先的次序遍历到第 k k k 个结点,我们删除这个结点之后会得到第 k k k 个结点的若干子树(每个子树都是一个连通块)以及一个包含第 k k k 个结点的父节点的连通块。

-
对于第 k k k 个结点的若干子树,我们可以通过递归的方式将子树的返回值设置为子树的节点数量,这样就可以非常高效地获取每个子树所对应的连通块的节点数量
-
而对于包含第 k k k 个结点的父节点的连通块,它的节点数量可以由如下公式计算 F = n − s u m − 1 F=n-sum-1 F=n−sum−1其中 n n n 为树的总节点数, s u m sum sum为所有子树构成的连通块的结点总数,1代表第 k k k 个结点
-
而我们的目标是求出将重心删除后,剩余各个连通块中点数的最大值,因此可以设置一个全局变量保存答案,然后在 D F S DFS DFS 的过程中不断更新它,具体更新的方式见代码。
-
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//树的重心,链式前向星,DFS
const int maxn = 1e5 + 1;
int n, head[maxn], len = 0, vis[maxn], ans = 1e6 - 5;struct Node {int to, next;
}e[2 * maxn];void add_edge(int u, int v) {e[++len].to = v;e[len].next = head[u];head[u] = len;
}int dfs(int k) {int son_max = 0, sum = 0;for (int i = head[k]; i; i = e[i].next) {int v = e[i].to;if (!vis[v]) {vis[v] = 1;int v_num = dfs(v);vis[v] = 0;sum += v_num;son_max = v_num > son_max ? v_num : son_max;}}// 更新答案ans = min(ans, max(son_max, n - sum - 1));return sum + 1;
}int main() {cin >> n;for (int i = 1; i < n; i++) {int u, v; cin >> u >> v;add_edge(u, v);add_edge(v, u);}dfs(1);cout << ans;return 0;
}
相关文章:
CSP复习每日一题(四)
树的重心 给定一颗树,树中包含 n n n 个结点(编号 1 ∼ n 1∼n 1∼n)和 n − 1 n−1 n−1条无向边。请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。 重心定义: 重心是指树中的一…...
dubbo之整合SpringBoot
目录 zookeeper安装 1.拉取ZooKeeper镜像 2.新建文件夹 3.挂载本地文件夹并启动服务 4.查看容器 5.进入容器(zookeeper) Dubbo Admin安装 1.下载dubbo-admin 2.zip包解压 3.修改配置文件 4.打包项目 5.启动jar 6.访问 构建项目 api模块 1.创建…...
UE 5 GAS 在项目中处理AttributeSet相关
这一篇文章是个人的实战经验记录,如果对基础性的内容不了解的,可以看我前面一篇文章对基础的概念以及内容的讲解。 设置AttributeSet 使用GAS之前,首先需要设置参数集AS,这个是用于同步的一些参数,至于如何设置GAS&a…...
JDBC数据库连接
目录 引言 一,基本概念 二,常用操作步骤 三,连接操作 引言 JDBC(Java DataBase Connectivity,java数据库连接)是一种用于执行SQL语句的Java API,可以为多种 关系数据库提供统一访问,它由一组用Java语言编写的类和接口…...
gitee分支合并
合并dev分支到master(合并到主分支) git checkout master git merge dev //这里的dev表示你的分支名称 git push //推送到远程仓库 效果如下图 不报错就表示推送成功了,希望能帮助各位小伙伴...
Python小白入门:文件、异常处理和json格式存储数据
这里写自定义目录标题 所用资料 一、从文件中读取数据1.1 读取整个文件1.2 文件路径1.3 逐行读取1.4 创建一个包含文件各行内容的列表1.5 使用文件的内容1.6 包含一百万位的大型文件1.7 圆周率值中包含你的生日吗练习题 二、写入文件2.1 写入空文件2.2 写入多行2.3 附加到文件练…...
16bit、8 通道、500kSPS、 SAR 型 ADC——MS5188N
MS5188N 是 8 通道、 16bit 、电荷再分配逐次逼近型模数 转换器,采用单电源供电。 MS5188N 拥有多通道、低功耗数据采集系统所需的所有 组成部分,包括:无失码的真 16 位 SAR ADC ;用于将输入配 置为单端输入࿰…...
Chapter 12: Regular expressions | Python for Everybody 讲义笔记_En
文章目录 Python for Everybody课程简介Regular ExpressionsRegular ExpressionsCharacter matching in regular expressionsExtracting data using regular expressionsCombining searching and extractingEscape characterSummaryBonus section for Unix / Linux usersDebugg…...
Android javaMail mergeDebugJavaResource FAILED解决
Java mail 引入这两个jar之后 implementation com.sun.mail:android-mail:1.6.7implementation com.sun.mail:android-activation:1.6.7build直接报错 > Task :app:mergeDebugJavaResource FAILED Execution failed for task :app:mergeDebugJavaResource. > A failure o…...
【ArcGIS Pro二次开发】(57):地图系列
在ArcGIS Pro中,有一个地图系列,可以在一个布局中导出多个地图。 在SDK中为ArcGIS.Desktop.layout.MapSeries类和映射系列导出选项,可以以支持多页导出。 MapSeries类提供了一个静态CreateSpatialMapSeries方法,该方法使用指定的…...
秋招打卡015(20230811)
文章目录 前言一、今天学习了什么?二、动态规划之股票问题1、总结2、题目 三、SQL总结 前言 提示:这里为每天自己的学习内容心情总结; Learn By Doing,Now or Never,Writing is organized thinking. 提示:…...
如何使用Word转PDF转换器在线工具?在线Word转PDF使用方法
Word转PDF转换器在线,是一种方便快捷的工具,可帮助您在不需要下载任何软件的情况下完成此任务。无论您是需要在工作中共享文档,还是将文件以PDF格式保存以确保格式不变,都可以依靠这款在线工具轻松完成转换。那么如何使用Word转PD…...
自然语言处理从入门到应用——LangChain:记忆(Memory)-[记忆的类型Ⅰ]
分类目录:《自然语言处理从入门到应用》总目录 会话缓存记忆ConversationBufferMemory 本节将介绍如何使用对话缓存记忆ConversationBufferMemory。这种记忆方式允许存储消息,并将消息提取到一个变量中,我们首先将其提取为字符串:…...
Camunda 7.x 系列【7】Spring Boot 集成 Camunda 7.19
有道无术,术尚可求,有术无道,止于术。 本系列Spring Boot 版本 2.7.9 本系列Camunda 版本 7.19.0 源码地址:https://gitee.com/pearl-organization/camunda-study-demo 文章目录 1. 前言2. Camunda Platform Run3. Spring Boot 版本兼容性4. 集成 Spring Boot5. 启动项目…...
24华东交通软件工程837考研题库
1.Jackson设计方法是由英国的M.Jackson所提出的。它是一种面向( )的软件设 计方法。 A.对象 B.数据流 C.数据结构 D.控制结构 答案:C 2.软件设计中,Jackson方法是一种面向…...
nginx 以及nginx优化
目录 nginx功能介绍 静态文件服务 反向代理 动态内容处理 SSL/TLS 加密支持 虚拟主机支持 URL 重写和重定向 缓存机制 日志记录 可扩展性和灵活性 nginx的主要应用场景 nginx常用命令 nginx另外一种安装方式 nginx常用的信号符: nginx配置文件详解 n…...
cesium学习记录04-坐标系
一、地理坐标系和投影坐标系的关系 地理坐标系 (Geographic Coordinate System, GCS) 定义:地理坐标系是一个基于三维地球表面的坐标系统。它使用经度和纬度来表示地点的位置。 特点: 使用经纬度来定义位置。 基于特定的地球参考椭球体。 适用于全球范…...
P5737 【深基7.例3】闰年展示
题目描述 输入 x , y x,y x,y,输出 [ x , y ] [x,y] [x,y] 区间中闰年个数,并在下一行输出所有闰年年份数字,使用空格隔开。 输入格式 输入两个正整数 x , y x,y x,y,以空格隔开。 输出格式 第一行输出一个正整数…...
Nacos的安装使用教程Linux
在 Linux 操作系统上安装和使用 Nacos 与 Windows 类似,以下是详细的步骤教程。我们将使用 Nacos 的 Standalone 模式进行安装和使用。请注意,对于生产环境,建议使用集群模式来实现高可用性和可扩展性。 步骤 1:准备环境 Java 安…...
数据结构-学习
参考: 数据结构-学习笔记_蓝净云_蓝净云的博客-CSDN博客...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
