F. Minimum Maximum Distance Codeforces Round 903 (Div. 3)

Problem - F - Codeforces

题目大意:有一棵n个点的树,其中有k个标记点,令点i到所有标记点的最远距离为fi,问所有点中fi的最小值是多少

1<=k<=n<=2e5

思路:我们首先考虑取得最小值的点在哪,我们假设这棵树是一条链,链上有两个标记点,如下图

显然,在标记点2、4之间的点是才可能是取得最小值的点,因为如果在某一个点一段的话,这个最大值一定大于两个标记点之间的距离,而在中间的点一定都是小于这个距离的,那么在这两个点之间很显然最中间的点是取得最小值的点。

所以取最小值的点一定在两个标记点的正中间,同时这两个标记点要距离最远,答案距离就是这个距离除以2向上取整。

要找两个距离最远的标记点,我们从任意一点i出发bfs找到一个最远的标记点j,这时有两种情况,一种就是这i,j就是距离最远的两个点,另一种情况是i在j和距离j更远的点k之间,

如上图,从4出发找到最远的点2,但右边的5距离2更远,这时候因为2已经是最靠左的一个点了,所以只要再从2再跑一遍bfs,找到的最远的点和2一定是距离最远的两个点,类似于问以哪个标记点为根,能找到根到标记点的最远距离。

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
vector<pair<int,int>>fac;
int tot = 0;
int n;
int head[N];
struct Edge
{int v, next;
}e[N*2];
int mark[N];
void addedge(int u, int v)
{e[++tot].v = v;e[tot].next = head[u];head[u] = tot;
}
bool vis[N];
void init()
{for (int i = 1; i <= n; i++){vis[i] = 0;head[i] = -1;mark[i] = 0;}
}
void solve()
{int m;cin >> n;cin >> m;init();int it1 = -1;for (int i = 1; i <= m; i++){int x;cin >> x;mark[x] = 1;if (it1 == -1)it1 = x;//任意找一个标记点作为起始根}for (int i = 1; i <= n - 1; i++){int u, v;cin >> u >> v;addedge(u, v);addedge(v, u);}if (m == 1){//如果只有1个标记点,那取最小值的点点就是那个标记点cout << 0 << '\n';return;}queue<pair<int, int>>q;q.push({ it1,0 });int ma = 0, mai;vis[it1] = 1;while (!q.empty()){//bfs找到距离根最远的点int u = q.front().first, nd = q.front().second;q.pop();for (int i = head[u]; ~i; i = e[i].next){int v = e[i].v;if (vis[v])continue;vis[v] = 1;q.push({ v,nd + 1 });if (mark[v] && nd + 1 > ma){ma = nd + 1, mai = v;}}}q.push({ mai,0 });//以之前找到的最远标记点为新根vis[mai] = 1;ma = 0, mai = -1;for (int i = 1; i <= n; i++){vis[i] = 0;}while (!q.empty()){int u = q.front().first, nd = q.front().second;q.pop();for (int i = head[u]; ~i; i = e[i].next){int v = e[i].v;if (vis[v])continue;vis[v] = 1;q.push({ v,nd + 1 });if (mark[v] && nd + 1 > ma){ma = nd + 1, mai = v;}}}cout << (ma - 1) / 2 + 1;//答案就是最远距离/2cout << '\n';
}
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);//FILE* stream1;//freopen_s(&stream1, "in.txt", "r", stdin);//freopen_s(&stream1, "out.txt", "w", stdout);int t;cin >> t;while (t--){solve();}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/161390.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Unity教程 ECS 内存分配器原理详解

一、UnityECS内存分配器的作用 在传统的面向对象编程模式中&#xff0c;我们通常使用堆内存来存储实体和组件数据。然而&#xff0c;由于实体和组件数据的规模通常非常庞大&#xff0c;使用堆内存进行分配和管理会导致内存碎片化和性能下降的问题。为了解决这个问题&#xff0…

常见的数据结构及应用

文章目录 前言数据结构介绍数组链表队列和栈树堆 总结 前言 数据结构是计算机存储、组织数据的方式。在工作中&#xff0c;我们通常会直接使用已经封装好的集合API&#xff0c;这样可以更高效地完成任务。但是作为一名程序员&#xff0c;掌握数据结构是非常重要的&#xff0c;…

MySQL——六、库表操作(下篇)

MySQL 一、INSERT语句二、REPLACE语句三、UPDATE语句四、delete和TRUNCATE语句五、MySQL用户授权1、密码策略2、用户授权和撤销授权 一、INSERT语句 #在表里面插入数据&#xff1a;默认情况下&#xff0c;一次插入操作只插入一行 方式1&#xff1a; INSERT [INTO] 表名 [(colu…

新一代开源语音库CoQui TTS冲到了GitHub 20.5k Star

Coqui TTS 项目介绍 Coqui 文本转语音&#xff08;Text-to-Speech&#xff0c;TTS&#xff09;是新一代基于深度学习的低资源零样本文本转语音模型&#xff0c;具有合成多种语言语音的能力。该模型能够利用共同学习技术&#xff0c;从各语言的训练资料集转换知识&#xff0c;来…

vue2 解密图片地址(url)-使用blob文件-打开png格式图片

一、背景 开发中需要对加密文件进行解码&#xff0c;如图片等静态资源。 根据后端给到的url地址&#xff0c;返回的是图片文件&#xff0c;但是乱码的&#xff0c;需要解码成png图片进行展示 二、请求接口 将后端返回的文件转为文件流&#xff0c;创建Blob对象来存储二进制…

设计模式:工厂方法模式(C#、JAVA、JavaScript、C++、Python、Go、PHP):

本节主要介绍设计模式中的工厂方法模式。 简介&#xff1a; 工厂方法模式&#xff0c;它是对简单工厂模式的进一步抽象化&#xff0c;其好处是可以使系统在不修改原来代码的情况下引进新的产品&#xff0c;即满足开闭原则。 它定义了一个用于创建对象的工厂接口&#xff0c;让…

游游的字母串 (环形数组两点之间的位置)

题目链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 题目&#xff1a; 样例&#xff1a; 输入 yab 输出 3 思路&#xff1a; 暴力枚举&#xff0c;全部变成对应的26个字母字符需要的操作步数&#xff0c;取最少的一个操作步数&#xff0c; 这里的操作步数&#xff0…

laravel中锁以及事务的简单使用

一、首先来说一下什么是共享锁&#xff1f;什么是排他锁&#xff1f; 共享&#xff1a;我可以读 写 加锁 , 别人可以 读 加锁。 排他&#xff1a;只有我 才 可以 读 写 加锁 , 也就是说&#xff0c;必须要等我提交事务&#xff0c;其他的才可以操作。 二、简单例子实现加锁 锁…

tomcat 服务器

tomcat 服务器 tomcat: 是一个开源的web应用服务器。区别nginx&#xff0c;nginx主要处理静态页面&#xff0c;那么动态请求&#xff08;连接数据库&#xff0c;动态页面&#xff09;并不是nginx的长处&#xff0c;动态的请求会交给tomcat进行处理。 nginx-----转发动态请求-…

PCL 坡度滤波算法地面分割(C++详细过程版)

目录 一、算法原理1、实现流程2、参考文献二、代码实现三、结果展示一、算法原理 1、实现流程 1、格网示意图 2、计算格网行列数 公式中的特殊符号为向上取整,

Cesium Vue(三)— 相机配置

1. 坐标系转换 1.1 cesium使用到的坐标系 屏幕坐标系&#xff0c;二维的笛卡尔坐标系&#xff0c;API > Cartesian2地理空间坐标系&#xff0c;WGS-84坐标系&#xff0c; API > Cartographic(经度&#xff0c;维度&#xff0c;高度)三维笛卡尔空间直角坐标系&#xff0…

GPT4 Advanced data analysis Code Interpreter 做行业数据分析、可视化处理图像、视频、音频等

1. 跨境电商如何用ChatGPT选品 ChatGPT Jungle scout 案例&#xff1a;跨境电商如何用ChatGFT选品 ChatGPTJungle scout 素材和资料来自&#xff1a; Jungle ScoutEM, Michael Soltis 和 文韬武韬AIGC 1.1 从Jungle scout上下载数据 Date Range > Last 90 days Downlo…

python+大数据校园卡数据分析 计算机竞赛

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 基于yolov5的深度学习车牌识别系统实现 &#x1f947;学长这里给一个题目综合评分(每项满分5分) 难度系数&#xff1a;4分工作量&#xff1a;4分创新点&#xff1a;3分 该项目较为新颖&am…

Stable Diffusion绘画,卡通,教室

1 girl, parted lips, blush, makeup, light smile, school uniform, classroom, light rays, glow, thighs, collarbone, narrow waist, (masterpiece), wallpaper 1个女孩&#xff0c;双唇&#xff0c;腮红&#xff0c;化妆&#xff0c;浅笑&#xff0c;校服&#xff0c;教室…

基于SSM框架的安全教育平台

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…

【Eclipse】设置自动提示

前言&#xff1a; eclipse默认有个快捷键&#xff1a;alt /就可以弹出自动提示&#xff0c;但是这样也太麻烦啦&#xff01;每次都需要手动按这个快捷键&#xff0c;下面给大家介绍的是&#xff1a;如何设置敲的过程中就会出现自动提示的教程&#xff01; 先按路线找到需要的页…

uniapp使用uQRCode绘制二维码,下载到本地,调起微信扫一扫二维码核销

1.效果 2.在utils文件夹下创建uqrcode.js // uqrcode.js //--------------------------------------------------------------------- // github https://github.com/Sansnn/uQRCode //---------------------------------------------------------------------let uQRCode {…

设计模式(1)-设计模式前置基础知识

1&#xff0c;设计模式概述 1.1 软件设计模式的产生背景 "设计模式"最初并不是出现在软件设计中&#xff0c;而是被用于建筑领域的设计中。 1977年美国著名建筑大师、加利福尼亚大学伯克利分校环境结构中心主任克里斯托夫亚历山大&#xff08;Christopher Alexand…

PS 学习笔记

书籍&#xff1a;Photoshop 2022从入门到精通-敬伟-微信读书 1. PS 常用快捷键 复位右侧基本工作栏&#xff1a;【窗口】-【工作区】- 【复位基本功能】 Ctrl 鼠标滚轮&#xff1a;主界面图片左右滚动Shift 鼠标滚轮&#xff1a;主界面图片上下滚动Alt 鼠标滚轮&#xff1…

算法通关村第19关【青铜】| 动态规划

动态规划&#xff08;Dynamic Programming&#xff0c;简称DP&#xff09;是一种解决多阶段决策过程最优化问题的数学方法。它通常用于解决那些具有重叠子问题和最优子结构性质的问题&#xff0c;这些问题可以分解为多个相互关联的子问题。 动态规划的核心思想是将原问题分解为…