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博客...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
