当前位置: 首页 > news >正文

CSP复习每日一题(四)

树的重心

给定一颗树,树中包含 n n n 个结点(编号 1 ∼ n 1∼n 1n)和 n − 1 n−1 n1条无向边。请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义: 重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。

输入格式

第一行包含整数 n n n,表示树的结点数。

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

输出格式

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

数据范围

1 ≤ n ≤ 105 1≤n≤105 1n105

输入样例

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=nsum1其中 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复习每日一题(四)

树的重心 给定一颗树&#xff0c;树中包含 n n n 个结点&#xff08;编号 1 ∼ n 1∼n 1∼n&#xff09;和 n − 1 n−1 n−1条无向边。请你找到树的重心&#xff0c;并输出将重心删除后&#xff0c;剩余各个连通块中点数的最大值。 重心定义&#xff1a; 重心是指树中的一…...

dubbo之整合SpringBoot

目录 zookeeper安装 1.拉取ZooKeeper镜像 2.新建文件夹 3.挂载本地文件夹并启动服务 4.查看容器 5.进入容器&#xff08;zookeeper&#xff09; Dubbo Admin安装 1.下载dubbo-admin 2.zip包解压 3.修改配置文件 4.打包项目 5.启动jar 6.访问 构建项目 api模块 1.创建…...

UE 5 GAS 在项目中处理AttributeSet相关

这一篇文章是个人的实战经验记录&#xff0c;如果对基础性的内容不了解的&#xff0c;可以看我前面一篇文章对基础的概念以及内容的讲解。 设置AttributeSet 使用GAS之前&#xff0c;首先需要设置参数集AS&#xff0c;这个是用于同步的一些参数&#xff0c;至于如何设置GAS&a…...

JDBC数据库连接

目录 引言 一&#xff0c;基本概念 二&#xff0c;常用操作步骤 三&#xff0c;连接操作 引言 JDBC(Java DataBase Connectivity,java数据库连接)是一种用于执行SQL语句的Java API&#xff0c;可以为多种 关系数据库提供统一访问&#xff0c;它由一组用Java语言编写的类和接口…...

gitee分支合并

合并dev分支到master&#xff08;合并到主分支&#xff09; git checkout master git merge dev //这里的dev表示你的分支名称 git push //推送到远程仓库 效果如下图 不报错就表示推送成功了&#xff0c;希望能帮助各位小伙伴...

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 、电荷再分配逐次逼近型模数 转换器&#xff0c;采用单电源供电。 MS5188N 拥有多通道、低功耗数据采集系统所需的所有 组成部分&#xff0c;包括&#xff1a;无失码的真 16 位 SAR ADC &#xff1b;用于将输入配 置为单端输入&#xff0…...

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中&#xff0c;有一个地图系列&#xff0c;可以在一个布局中导出多个地图。 在SDK中为ArcGIS.Desktop.layout.MapSeries类和映射系列导出选项&#xff0c;可以以支持多页导出。 MapSeries类提供了一个静态CreateSpatialMapSeries方法&#xff0c;该方法使用指定的…...

秋招打卡015(20230811)

文章目录 前言一、今天学习了什么&#xff1f;二、动态规划之股票问题1、总结2、题目 三、SQL总结 前言 提示&#xff1a;这里为每天自己的学习内容心情总结&#xff1b; Learn By Doing&#xff0c;Now or Never&#xff0c;Writing is organized thinking. 提示&#xff1a…...

如何使用Word转PDF转换器在线工具?在线Word转PDF使用方法

Word转PDF转换器在线&#xff0c;是一种方便快捷的工具&#xff0c;可帮助您在不需要下载任何软件的情况下完成此任务。无论您是需要在工作中共享文档&#xff0c;还是将文件以PDF格式保存以确保格式不变&#xff0c;都可以依靠这款在线工具轻松完成转换。那么如何使用Word转PD…...

自然语言处理从入门到应用——LangChain:记忆(Memory)-[记忆的类型Ⅰ]

分类目录&#xff1a;《自然语言处理从入门到应用》总目录 会话缓存记忆ConversationBufferMemory 本节将介绍如何使用对话缓存记忆ConversationBufferMemory。这种记忆方式允许存储消息&#xff0c;并将消息提取到一个变量中&#xff0c;我们首先将其提取为字符串&#xff1a…...

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&#xff0e;Jackson设计方法是由英国的M&#xff0e;Jackson所提出的。它是一种面向( )的软件设 计方法。 A&#xff0e;对象 B&#xff0e;数据流 C&#xff0e;数据结构 D&#xff0e;控制结构 答案:C 2&#xff0e;软件设计中&#xff0c;Jackson方法是一种面向…...

nginx 以及nginx优化

目录 nginx功能介绍 静态文件服务 反向代理 动态内容处理 SSL/TLS 加密支持 虚拟主机支持 URL 重写和重定向 缓存机制 日志记录 可扩展性和灵活性 nginx的主要应用场景 nginx常用命令 nginx另外一种安装方式 nginx常用的信号符&#xff1a; nginx配置文件详解 n…...

cesium学习记录04-坐标系

一、地理坐标系和投影坐标系的关系 地理坐标系 (Geographic Coordinate System, GCS) 定义&#xff1a;地理坐标系是一个基于三维地球表面的坐标系统。它使用经度和纬度来表示地点的位置。 特点&#xff1a; 使用经纬度来定义位置。 基于特定的地球参考椭球体。 适用于全球范…...

P5737 【深基7.例3】闰年展示

题目描述 输入 x , y x,y x,y&#xff0c;输出 [ x , y ] [x,y] [x,y] 区间中闰年个数&#xff0c;并在下一行输出所有闰年年份数字&#xff0c;使用空格隔开。 输入格式 输入两个正整数 x , y x,y x,y&#xff0c;以空格隔开。 输出格式 第一行输出一个正整数&#xf…...

Nacos的安装使用教程Linux

在 Linux 操作系统上安装和使用 Nacos 与 Windows 类似&#xff0c;以下是详细的步骤教程。我们将使用 Nacos 的 Standalone 模式进行安装和使用。请注意&#xff0c;对于生产环境&#xff0c;建议使用集群模式来实现高可用性和可扩展性。 步骤 1&#xff1a;准备环境 Java 安…...

数据结构-学习

参考&#xff1a; 数据结构-学习笔记_蓝净云_蓝净云的博客-CSDN博客...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...