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

Codeforces Round 936 (Div. 2)

C. Tree Cutting

题意:给定一棵树,需要删除 k 条边,使得 k+1 个联通块中的最小结点数最大。求出这个最大值

思路:求最小值最大--想到二分答案--然后深搜满足条件的连通块是否大于k即可

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<int>v[N];
int n,k,cnt;
dfs(int u,int father,int mid)
{//返回的是每个子树节点的个数 若有子树节点符合mid 则切一刀 返回0int res=1;//自身的节点个数为1 从上到下 从下返回 记录节点个数for(int i=0;i<v[u].size();i++){int j=v[u][i];if(j==father) continue;//如果是自己的父亲节点就不深搜下取res+=dfs(j,u,mid);}if(res>=mid){res=0;cnt++;}return res;
}
bool check(int mid)
{cnt=0;dfs(1,0,mid);if(cnt>k) return true;return false;
}
int main()
{int t;cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++) v[i].clear();for(int i=1;i<n;i++){int a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}int l=0,r=n+1;while(l<r){int mid=(l+r+1)>>1;if(check(mid)) l=mid;else r=mid-1;}cout<<l<<endl;}return 0;
}

相关文章:

Codeforces Round 936 (Div. 2)

C. Tree Cutting 题意&#xff1a;给定一棵树&#xff0c;需要删除 k 条边&#xff0c;使得 k1 个联通块中的最小结点数最大。求出这个最大值 思路&#xff1a;求最小值最大--想到二分答案--然后深搜满足条件的连通块是否大于k即可 #include<iostream> #include<al…...

yolov6实现遥感影像目标识别|以DIOR数据集为例

1 目标检测是计算机视觉领域中的一项重要任务&#xff0c;它的目标是在图像或视频中检测出物体的位置和类别。YOLO&#xff08;You Only Look Once&#xff09;是一系列经典的目标检测算法&#xff0c;最初由Joseph Redmon等人于2016年提出。YOLO算法具有快速、简单、端到端的特…...

stable-diffusion-electron-clickstart 支持windows AMD显卡

前言 使用vue3 vite electron element-plus构建&#xff0c;正好学习下electrongithub stable-diffusion “画境导航者” 启动器 简介 stable-diffusion “画境导航者” 启动器支持功能 一键启动打开文件夹&#xff08;tmp、txt2img-images&#xff09;等模型所在文件夹&…...

ES进程除了kill之外,有什么优雅关闭的方式吗?

问题 Linux环境中&#xff0c;Elasticsearch 8的进程除了kill之外&#xff0c;有什么优雅关闭的方式吗&#xff1f; 具体实施方式 在Linux环境中&#xff0c;Elasticsearch&#xff08;ES&#xff09;进程可以通过多种方式实现优雅关闭&#xff0c;这种方式允许它完成必要的…...

院子摄像头的监控

院子摄像头的监控和禁止区域入侵检测相比&#xff0c;多了2个功能&#xff1a;1&#xff09;如果检测到有人入侵&#xff0c;则把截图保存起来&#xff0c;2&#xff09;如果检测到有人入侵&#xff0c;则向数据库插入一条事件数据。 打开checkingfence.py&#xff0c;添加如下…...

SpringBoot3使用响应Result类返回的响应状态码为406

Resolved [org.springframework.web.HttpMediaTypeNotAcceptableException: No acceptable representation] 解决方法&#xff1a;Result类上加上Data注解...

基础:TCP四次挥手做了什么,为什么要挥手?

1. TCP 四次挥手在做些什么 1. 第一次挥手 &#xff1a; 1&#xff09;挥手作用&#xff1a;主机1发送指令告诉主机2&#xff0c;我没有数据发送给你了。 2&#xff09;数据处理&#xff1a;主机1&#xff08;可以是客户端&#xff0c;也可以是服务端&#xff09;&#xff0c…...

Android Studio实现内容丰富的安卓校园二手交易平台(带聊天功能)

获取源码请点击文章末尾QQ名片联系&#xff0c;源码不免费&#xff0c;尊重创作&#xff0c;尊重劳动 项目编号083 1.开发环境android stuido jdk1.8 eclipse mysql tomcat 2.功能介绍 安卓端&#xff1a; 1.注册登录 2.查看二手商品列表 3.发布二手商品 4.商品详情 5.聊天功能…...

第十一届蓝桥杯省赛第一场真题

2065. 整除序列 - AcWing题库 #include <bits/stdc.h> using namespace std; #define int long long//记得开long long void solve(){int n;cin>>n;while(n){cout<<n<< ;n/2;} } signed main(){int t1;while(t--)solve();return 0; } 2066. 解码 - …...

设计模式 模板方法模式

01.如果接到一个任务&#xff0c;要求设计不同型号的悍马车 02.设计一个悍马车的抽象类&#xff08;模具&#xff0c;车模&#xff09; public abstract class HummerModel {/** 首先&#xff0c;这个模型要能够被发动起来&#xff0c;别管是手摇发动&#xff0c;还是电力发动…...

【STM32嵌入式系统设计与开发】——6矩阵按键应用(4x4)

这里写目录标题 一、任务描述二、任务实施1、SingleKey工程文件夹创建2、函数编辑&#xff08;1&#xff09;主函数编辑&#xff08;2&#xff09;LED IO初始化函数(LED_Init())&#xff08;3&#xff09;开发板矩阵键盘IO初始化&#xff08;ExpKeyBordInit()&#xff09;&…...

乐优商城(九)数据同步RabbitMQ

1. 项目问题分析 现在项目中有三个独立的微服务&#xff1a; 商品微服务&#xff1a;原始数据保存在 MySQL 中&#xff0c;从 MySQL 中增删改查商品数据。搜索微服务&#xff1a;原始数据保存在 ES 的索引库中&#xff0c;从 ES 中查询商品数据。商品详情微服务&#xff1a;做…...

XSS-labs详解

xss-labs下载地址https://github.com/do0dl3/xss-labs 进入靶场点击图片&#xff0c;开始我们的XSS之旅&#xff01; Less-1 查看源码 代码从 URL 的 GET 参数中取得 "name" 的值&#xff0c;然后输出一个居中的标题&#xff0c;内容是 "欢迎用户" 后面…...

设计模式——模板方法模式封装.net Core读取不同类型的文件

1、模板方法模式 模板方法模式&#xff1a;定义一个操作中的算法骨架&#xff0c;而将一些步骤延迟到子类中&#xff0c;模板方法使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。 特点&#xff1a;通过把不变的行为搬移到超类&#xff0c;去除子类中重复的代…...

[思考记录]技术欠账

最近对某开发项目做回顾梳理&#xff0c;除了进一步思考整理相关概念和问题外&#xff0c;一个重要的任务就是清理“技术欠账”。 这个“技术欠账”是指在这个项目的初期&#xff0c;会有意无意偏向快速实现&#xff0c;想先做出来、用起来&#xff0c;进而在实现过程中做出…...

React - 实现菜单栏滚动

简介 本文将会基于react实现滚动菜单栏功能。 技术实现 实现效果 点击菜单&#xff0c;内容区域会自动滚动到对应卡片。内容区域滑动&#xff0c;指定菜单栏会被选中。 ScrollMenu.js import {useRef, useState} from "react"; import ./ScrollMenu.css;export co…...

线性筛选(欧拉筛选)-洛谷P3383

#include <bits/stdc.h> using namespace std; int main() {std::ios::sync_with_stdio(false); cin.tie(nullptr); //为了加速int n, q;cin >> n >> q; vector<int>num(n 1); //定义数字表vector<int>prime; //定义素数表数组num[1] …...

企业微信可以更换公司主体吗?

企业微信变更主体有什么作用&#xff1f;当我们的企业因为各种原因需要注销或已经注销&#xff0c;或者运营变更等情况&#xff0c;企业微信无法继续使用原主体继续使用时&#xff0c;可以申请企业主体变更&#xff0c;变更为新的主体。企业微信变更主体的条件有哪些&#xff1…...

Qt教程 — 3.6 深入了解Qt 控件:Display Widgets部件(2)

目录 1 Display Widgets简介 2 如何使用Display Widgets部件 2.1 QTextBrowser组件-简单的文本浏览器 ​2.2 QGraphicsView组件-简单的图像浏览器 Display Widgets将分为两篇文章介绍 文章1&#xff08;Qt教程 — 3.5 深入了解Qt 控件&#xff1a;Display Widgets部件-CSDN…...

Golang案例开发之gopacket抓包三次握手四次分手(3)

文章目录 前言一、理论知识三次握手四次分手二、代码实践1.模拟客户端和服务器端2.三次握手代码3.四次分手代码验证代码完整代码总结前言 TCP通讯的三次握手和四次分手,有很多文章都在介绍了,当我们了解了gopacket这个工具的时候,我们当然是用代码实践一下,我们的理论。本…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

数据结构:递归的种类(Types of Recursion)

目录 尾递归&#xff08;Tail Recursion&#xff09; 什么是 Loop&#xff08;循环&#xff09;&#xff1f; 复杂度分析 头递归&#xff08;Head Recursion&#xff09; 树形递归&#xff08;Tree Recursion&#xff09; 线性递归&#xff08;Linear Recursion&#xff09;…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”

案例&#xff1a; 某医药分销企业&#xff0c;主要经营各类药品的批发与零售。由于药品的特殊性&#xff0c;效期管理至关重要&#xff0c;但该企业一直面临效期问题的困扰。在未使用WMS系统之前&#xff0c;其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...

Easy Excel

Easy Excel 一、依赖引入二、基本使用1. 定义实体类&#xff08;导入/导出共用&#xff09;2. 写 Excel3. 读 Excel 三、常用注解说明&#xff08;完整列表&#xff09;四、进阶&#xff1a;自定义转换器&#xff08;Converter&#xff09; 其它自定义转换器没生效 Easy Excel在…...

第22节 Node.js JXcore 打包

Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本&#xff0c;基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...