当前位置: 首页 > 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这个工具的时候,我们当然是用代码实践一下,我们的理论。本…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...