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

搜索与图论:树的重心

搜索与图论:树的重心

    • 题目描述
    • 参考代码

题目描述

在这里插入图片描述
输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例

4

参考代码

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010, M = N * 2;int n, m;
int h[N], e[M], ne[M], idx;
bool st[N];int ans = N;void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}// 以u为根的子树中点的数量
int dfs(int u)
{st[u] = true;   // 标记一下,已经被搜过了int sum = 1, res = 0;for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (!st[j]){int s = dfs(j);res = max(res, s);sum += s;}}res = max(res, n - sum);ans = min(ans, res);return sum;
}int main()
{   cin >> n >> m;memset(h, -1, sizeof h);for (int i = 0; i < n; i++){int a, b;cin >> a >> b;add(a, b), add(b, a);}dfs(1);cout << ans << endl;return 0;
}

相关文章:

搜索与图论:树的重心

搜索与图论&#xff1a;树的重心 题目描述参考代码 题目描述 输入样例 9 1 2 1 7 1 4 2 8 2 5 4 3 3 9 4 6输出样例 4参考代码 #include <cstring> #include <iostream> #include <algorithm>using namespace std;const int N 100010, M N * 2;int n, m…...

程序代写,代码编写

Java 项目代做&#xff0c;小程序&#xff0c;安卓&#xff0c;鸿蒙&#xff0c;VUE 程序代写 Java调试安装、项目运行、代码代做、环境配置、工具安装、代码讲解、代码调试、代码运行、代码部署、项目调试、项目部署、Java Web、Spring Boot、项目设计、前后端分离、代码报错解…...

PbootCms微信小程序官网模版/企业官网/社交电商官网/网络工作室/软件公司官网

在数字化时代&#xff0c;企业网站已成为吸引潜在客户、提升企业形象、和扩大品牌影响力的必备工具。因此&#xff0c;一个优秀的企业网站模板显得尤为重要。 企业官网的内容框架通常都包含企业形象、产品或服务类型、信息展示等部分&#xff0c;设计师需要借助和企业形象契合…...

【机器学习】GLM4-9B-Chat大模型/GLM-4V-9B多模态大模型概述、原理及推理实战

​​​​​​​ 目录 一、引言 二、模型简介 2.1 GLM4-9B 模型概述 2.2 GLM4-9B 模型架构 三、模型推理 3.1 GLM4-9B-Chat 语言模型 3.1.1 model.generate 3.1.2 model.chat 3.2 GLM-4V-9B 多模态模型 3.2.1 多模态模型概述 3.2.2 多模态模型实践 四、总结 一、引言…...

Kotlin 函数式接口

文章目录 定义实例化Kotlin 调用 Java 单抽象方法接口 定义 在 Kotlin 中&#xff0c;如果一个接口只有一个抽象方法&#xff08;其他非抽象成员数量不限&#xff09;&#xff0c;可以写成类似函数的形式。 fun interface Editable {// 此处 abstract 可省略abstract fun edi…...

【数据结构】平衡二叉树(AVL树)

目录 前言 一、AVL树概念 二、AVL树节点定义 三、AVL树插入 1. 按照二叉搜索树的方式插入新节点 2. 维护节点的平衡因子与调整树的结构 a. 新节点插入较高左子树的左侧---左左&#xff1a;右单旋 b. 新节点插入较高右子树的右侧---右右&#xff1a;左单旋 c. 新节点插入…...

python数据文件处理库-pandas

内容目录 一、pandas介绍二、数据加载和写出三、数据清洗四、数据转换五、数据查询和筛选六、数据统计七、数据可视化 pandas 是一个 Python提供的快速、灵活的数据结构处理包&#xff0c;让“关系型”或“标记型”数据的交互既简单又直观。 官网地址: https://pandas.pydata.o…...

stm32 h5 串口采用DMA循环BUFF接收数据

当使用STM32H5系列的MCU进行串口&#xff08;USART&#xff09;通信&#xff0c;并希望使用DMA&#xff08;Direct Memory Access&#xff09;进行循环缓冲区&#xff08;Circular Buffer&#xff09;接收数据时&#xff0c;你需要进行以下配置步骤&#xff1a; 初始化串口&…...

海外媒体通稿:9个极具创意的旅游业媒体推广案例分享-华媒舍

如今&#xff0c;旅游业正迅速发展&#xff0c;媒体推广成为吸引游客的关键。为了更好地展示旅游目的地&#xff0c;许多创意而富有创新的媒体推广策略应运而生。本文将介绍九个极富创意的旅游业媒体推广案例&#xff0c;为广大从业者带来灵感和借鉴。 1. 视频系列&#xff1a;…...

接口自动化框架封装思想建立(全)

httprunner框架&#xff08;上&#xff09; 一、什么是Httprunner&#xff1f; 1.httprunner是一个面向http协议的通用测试框架&#xff0c;以前比较流行的是2.X版本。 2.他的思想是只需要维护yaml/json文件就可以实现接口自动化测试&#xff0c;性能测试&#xff0c;线上监…...

char [] 赋新值

在C语言中&#xff0c;字符数组&#xff08;char []&#xff09;的值可以通过多种方式进行赋值。以下是一些常见的方法&#xff1a; 1、直接初始化&#xff1a; char str[50] "Hello, World!";2、使用strcpy()函数&#xff1a; char str[50]; strcpy(str, "…...

matlab计算图像信噪比SNR

直接上源码: close all clear all clc% 读取图像 I = imread(lena.bmp);I = rgb2gray(I); J =imnoise(I, salt & pepper, 0.001);...

DP读书:如何使用badge?(开源项目下的标咋用)

最近在冲论坛&#xff0c;很少更一些内容了。但遇到了一个真的有趣的&#xff1a; 开源项目下&#xff0c;蓝蓝绿绿的标是怎么用的呢&#xff1f; 这是我的主页Readme&#xff0c;在看一些NXP的主仓时&#xff0c;突然发现没有这个玩&#xff0c;就自己整了个 再比如我的CSDN专…...

使用JavaScript实现网页通知功能

如何使用js来实现网页通知功能。即使在用户浏览其他页面时&#xff0c;也能向他们推送通知信息。 废话不多说直接上代码 function showAutoNotification() {if ("Notification" in window) {Notification.requestPermission().then(function(permission) {if (permis…...

前端--导出

这边记录我们公司后端做的导出接口和前端是如何对接的 这边的技术栈是&#xff1a; 1&#xff1a; react 2&#xff1a; fetch 第一步&#xff1a;简单封装--导出界面 import { DrawerForm } from ant-design/pro-components; import { CloseOutlined } f…...

【数据库系统概论】触发器

【数据库系统概论】触发器 概述 在数据库系统中&#xff0c;触发器&#xff08;Trigger&#xff09;是一种特殊的存储过程&#xff0c;当特定事件在数据库表上发生时&#xff0c;会自动执行。触发器主要用于确保数据的完整性、一致性和实现复杂的业务规则。触发器是由用户定义…...

小白跟做江科大32单片机之按键控制LED

原理部分 1.LED部分使用的是这样的连接方式 2.传感器模块的电路图 滤波电容如果接地&#xff0c;一般用于滤波&#xff0c;在分析电路时就不用考虑。下面这个电路就是看A端和B端哪端的拉力大&#xff0c;就能把电压值对应到相应的电压值 比较器部分 如果A端电压>B端电压&am…...

每天写java到期末考试(6.6)-java文件输入输出流实验

1、用字节流读写二进制文件 要求:用DataOutputStreamFileOutputStream类将1,2,…,100,这100个数字写入到文件 d:\out1.bin里,然后再用DatalnputStreamFilelnputStream类将d:\out1.bin的内读出来,并输出到屏幕上。 用DataOutputStreamFileOutputStream写入二进制数据时,直接调…...

Word2021中的The Mathtype DLL cannot be found问题解决(office 16+mathtype7+非初次安装)

问题描述&#xff0c;我的问题发生在word中无法使用自定义功能区中的mathtype 我的环境是&#xff1a;W11Word2021mathtype7 因为我是第二次安装mathtype7&#xff0c;所以我怀疑是因为没有卸载干净&#xff0c;于是我参考了下面这篇文章的做法 参考文章 1.首先重新卸载当前的…...

【Android面试八股文】在Java中传参数时是将值进行传递,还是传递引用?

在Java中传参数时是将值进行传递,还是传递引用? 这道题想考察什么? 是否了解什么是值传递和引用传递与真实场景使用,是否熟悉什么是值传递和引用传递在工作中的表现是什么? 考察的知识点 什么是值传递和引用传递的概念,两者对开发中编写的代码的影响 考生应该如何回…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

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

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

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...