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

【简单图论】CF898 div4 H

Problem - H - Codeforces

题意:

思路:

手玩一下样例就能发现简单结论:

v 离它所在的树枝的根的距离 < m 离这个根的距离时是 YES

否则就是NO

实现就很简单,先去树上找环,然后找出这个根,分别给a 和 b BFS一遍,得出两个dis数组,比较一下即可

对于只有的环情况 和 m = v 的情况需要特判

Code:

#include <bits/stdc++.h>constexpr int N = 2e5 + 10;
constexpr int M = 1e6 + 10;
constexpr int Inf = 1e9;std::queue<int> q1, q2;
std::vector<int> adj[N];int n, a, b;
int top = 0;
int u[N], v[N];
int st[N], r[N];
int dis1[N];
int dis2[N];int find_r(int u, int fa) {if (st[u]) return u;st[u] = 1;for (auto v : adj[u]) {if (v == fa) continue;int t = find_r(v, u);if (t) {r[++ top] = u;st[u] = 2;return t == u ? 0 : t;}}return 0;
}
void bfs1(int u) {memset(dis1, 0x3f, sizeof(dis1));dis1[u]= 0;q1.push(u);while(!q1.empty()) {int u = q1.front();q1.pop();for (auto v : adj[u]) {if (dis1[v] > dis1[u] + 1) {dis1[v] = dis1[u] + 1;q1.push(v);}}}
}
void bfs2(int u) {memset(dis2, 0x3f, sizeof(dis2));dis2[u] = 0;q2.push(u);while(!q2.empty()) {int u = q2.front();q2.pop();for (auto v : adj[u]) {if (dis2[v] > dis2[u] + 1) {dis2[v] = dis2[u] + 1;q2.push(v);}}}
}
void solve() {std::cin >> n >> a >> b;top = 0;while(!q1.empty()) q1.pop();while(!q2.empty()) q2.pop();for (int i = 1; i <= n; i ++) {st[i] = 0;adj[i].clear();}for (int i = 1; i <= n; i ++) {std::cin >> u[i] >> v[i];adj[u[i]].push_back(v[i]);adj[v[i]].push_back(u[i]);}if (a == b) {std::cout << "NO" << "\n";return;}find_r(1, 0);bfs1(b);int miu1 = Inf, ansu = 0;for (int i = 1; i <= n; i ++) {if (st[i] == 2 && miu1 > dis1[i]) {miu1 = dis1[i];ansu = i;}}if (st[b] == 2) {std::cout << "YES" << "\n";return;}bfs2(a);int ans1 = dis2[ansu];int ans2 = miu1;if (ans1 > ans2) std::cout << "YES" << "\n";else std::cout << "NO" << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while(t --) {solve();}return 0;
}

 

相关文章:

【简单图论】CF898 div4 H

Problem - H - Codeforces 题意&#xff1a; 思路&#xff1a; 手玩一下样例就能发现简单结论&#xff1a; v 离它所在的树枝的根的距离 < m 离这个根的距离时是 YES 否则就是NO 实现就很简单&#xff0c;先去树上找环&#xff0c;然后找出这个根&#xff0c;分别给a 和…...

【大虾送书第十一期】适合新手自学的网络安全基础技能“蓝宝书”:《CTF那些事儿》

目录 &#x1f96e;写在前面 &#x1f96e;内容简介 &#x1f96e;读者对象 &#x1f96e;专家推荐 &#x1f96e;目录 &#x1f96e;文末福利 &#x1f990;博客主页&#xff1a;大虾好吃吗的博客 &#x1f990;专栏地址&#xff1a;免费送书活动专栏地址 写在前面 CTF比赛是快…...

IDEA安装离线插件后重启无法打开

解决方法 1.找到插件安装目录删除插件 插件的位置一般在C:\Users\19058\AppData\Roaming\JetBrains\IntelliJIdea2021.1\plugins 高亮部分是自己电脑的用户位置&#xff0c;把报错前的刚才最新安装的插件删除&#xff0c;再尝试打开idea即可解决该问题 2.补充说明 AppData是个隐…...

论软件的可靠性设计

摘要 2021年6月&#xff0c;我所在的公司中标某集团保险大数据平台一体化研发项目&#xff0c;该项目总投资2000万人民币&#xff0c;项目周期为2年&#xff0c;通过该项目&#xff0c;搭建该集团保险大数据平台&#xff0c;一方面将全国所有保险业务全部入库并保存&#xff0…...

AG35学习笔记(一):debug串口抓取模组log、debug串口测试AT指令、echo命令通过串口发送16进制数据

目录 一、概述二、抓取模组log2.1 硬件接口2.2 用户登录2.3 相关指令 三、测试AT指令3.1 查看端口3.2 进入模式 四、串口发16进制echo使用 一、概述 二、抓取模组log 在之前记录了通过USB&#xff0c;使用移远工具Qwinlog来抓取log&#xff08;3.3 抓取模组log&#xff09;。…...

Python进阶学习----一闭三器

目录 ​编辑 前言 一.三器 1. 迭代器&#xff08;Iterator&#xff09; 1.1 什么是可迭代对象 1.2什么是迭代器 1.3案例演示&#xff1a; 以下是一个简单的迭代器示例&#xff0c;遍历一个列表并打印每个元素&#xff1a; 1.4迭代器总结 2. 生成器&#xff08;Generat…...

C/S架构学习之TCP客户端

TCP客户端的实现流程&#xff1a;一、创建套接字&#xff08;socket函数&#xff09;&#xff1a;通信域选择IPV4网络协议、流式套接字&#xff1b; int sockfd socket(AF_INET,SOCK_STREAM,0); 二、填充服务器的网络信息结构体&#xff08;struct sockaddr_in serveraddr&…...

系统集成|第十二章(笔记)

目录 第十二章 沟通管理12.1 沟通的基本概念12.2 主要过程12.2.1 规划沟通管理12.2.2 管理沟通12.2.3 控制沟通 12.3 常见问题 上篇&#xff1a;第十一章、项目人力资源管理 第十二章 沟通管理 沟通管理在项目计划、执行、监控过程中具有重要的作用&#xff0c;项目经理应该拿…...

图神经网络(GNN)最新顶会论文汇总【附源码】

得益于强大的建模和分析能力&#xff0c;图神经网络&#xff08;GNN&#xff09;在社交网络分析、推荐系统、知识图谱、文本分析、等诸多领域得到了广泛的应用&#xff0c;目前已成为了人工智能领域的热门研究方向。 在今年的各大顶会获奖论文中&#xff0c;图神经网络相关的论…...

【算法】算法设计与分析 课程笔记 第二章 递归与分治策略

2.1 递归 直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 2.1.1 阶乘 首先得想到一个求阶乘的函数&#xff1a; 这个函数的下面那个式子就用到了调用自身&#xff0c;所以可以用递归来实现&#xff0c;将主问题拆分成若干层的子问题&am…...

Java客户端_Apache Curator操作Zookeeper

Curator是 Netflix公司开源的一套ZooKeeper客户端框架。和ZkClient一样&#xff0c;Curator解决了很多ZooKeeper客户端非常底层的细节开发工作&#xff0c;包括连接重连、反复注册Watcher和 NodeExistsException异常等&#xff0c;目前已经成为了Apache的顶级项目,是全世界范围…...

14:00面试,14:07就出来了,问的问题有点变态

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到8月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%,…...

《你好,C语言》:从另一个视角学习并重新审视C语言的意义

《你好&#xff0c;C语言》&#xff1a;从另一个视角学习并重新审视C语言的意义 尽管C语言诞生了这么多年&#xff0c;但是它依然活跃在开发者一线&#xff0c;不可否认的是C语言的确有它独特的魅力。本文将从一个全新的视角&#xff0c;重新带领大家学习领悟C语言的奥秘&#…...

信创之国产浪潮电脑+统信UOS操作系统体验1:硬件及软件常规功能支持情况介绍

一、引言 由于公司要求支持国产信创&#xff0c;最近办公的笔记本电脑换成了软硬件全国产&#xff0c;由于国产操作系统是在开源linux基础上演进的&#xff0c;在换之前&#xff0c;非常担心操作不方便&#xff0c;周边应用软件少&#xff0c;功能差&#xff0c;内心是比较抗拒…...

JAVA学习-全网最详细

&#x1f308;write in front&#x1f308; &#x1f9f8;大家好&#xff0c;我是Aileen&#x1f9f8;.希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流. &#x1f194;本文由Aileen_0v0&#x1f9f8; 原创 CSDN首发&#x1f412; 如…...

基于物联网的农村地区智能微电网系统(Simulink)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

JavaScript系列从入门到精通系列第九篇:JavaScript中赋值运算符和关系运算符以及Unicode编码介绍

一&#xff1a;赋值运算符 1&#xff1a; 右侧的值可以赋值给左侧的变量。 var a 123; console.log(a);//123 2&#xff1a; var a 10; a a 5; a 5; 上边这两个写法是一样的。 3&#xff1a;- var a 10; a a-5; a - 5; 上边这两个写法是一样的。 4&#xff1a;* …...

租用独立服务器有哪些常见的误区?

租用独立服务器有哪些常见的误区&#xff1f; 如今&#xff0c;租用独立服务器的市场随着idc行业良好的发展趋势而变得越来越广泛&#xff0c;其最明显的地方在于出现了许多的代理商&#xff0c;而成为代理商的门槛非常低&#xff0c;这样一来就会出现许多问题&#xff0c;导致…...

【学习笔记】POJ 3834 graph game

点这里 结论题&#x1f605; &#xff0c;图一乐 结论&#xff1a;如果原图中存在两个边集不交的生成树&#xff0c;那么 Bob \text{Bob} Bob必胜&#xff1b;否则 Alice \text{Alice} Alice必胜 证明有点难&#x1f605; 首先&#xff0c;考虑维护两颗 不存在红边 的生成树…...

无监督学习算法Kmeans

1. 有监督学习和无监督学习 在机器学习算法中&#xff0c;常把算法分为有监督学习和无监督学习两种。他们之间的区别主要在于输入数据集类型和学习目标。 &#xff08;1&#xff09;有监督学习&#xff1a;训练输入的数据需要带有标签&#xff0c;以便算法能够学习输入和输出…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...