当前位置: 首页 > 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博客...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

【免费数据】2005-2019年我国272个地级市的旅游竞争力多指标数据(33个指标)

旅游业是一个城市的重要产业构成。旅游竞争力是一个城市竞争力的重要构成部分。一个城市的旅游竞争力反映了其在旅游市场竞争中的比较优势。 今日我们分享的是2005-2019年我国272个地级市的旅游竞争力多指标数据&#xff01;该数据集源自2025年4月发表于《地理学报》的论文成果…...

Springboot 高校报修与互助平台小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;高校报修与互助平台小程序被用户普遍使用&#xff0c;为…...