P3398 仓鼠找 sugar
Portal.
LCA。
询问树上两条路径是否有交点。
画图发现无非两种情况:

发现一条路径的起点和终点的 LCA 经过另一条路径,是两路径相交的充要条件。
考虑如何判断这个 LCA 在不在路径上。若 d ( s , LCA ) + d ( LCA , t ) = d ( s , t ) d(s,\text{LCA})+d(\text{LCA},t)=d(s,t) d(s,LCA)+d(LCA,t)=d(s,t),由于树上路径的唯一性,显然存在。
注意 LCA 函数,if(dep[f[x][i]]>=dep[y]) x x x 就可以往上跳。
#include <bits/stdc++.h>
using namespace std;
#define int long longconst int maxn=1e5+5;
struct edge{int to,nxt;}e[maxn*2];
int head[maxn],cnt,dep[maxn],f[maxn][25];void add(int x,int y){e[++cnt]={y,head[x]},head[x]=cnt;}void dfs(int x,int fa)
{dep[x]=dep[fa]+1,f[x][0]=fa;for(int i=head[x];i;i=e[i].nxt){if(e[i].to==fa) continue;dfs(e[i].to,x);}
}int lca(int x,int y)
{if(dep[x]<dep[y]) swap(x,y);for(int i=20;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];if(x==y) return x;for(int i=20;i>=0;i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}int dis(int x,int y){return abs(dep[x]-dep[lca(x,y)])+abs(dep[y]-dep[lca(x,y)]);}signed main()
{int n,q;cin>>n>>q;for(int i=1,u,v;i<n;i++) cin>>u>>v,add(u,v),add(v,u);dfs(1,0);for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];while(q--){int a,b,c,d;cin>>a>>b>>c>>d;int f1=lca(a,b),f2=lca(c,d);if(dis(a,f2)+dis(b,f2)==dis(a,b)||dis(c,f1)+dis(d,f1)==dis(c,d)) cout<<"Y\n";else cout<<"N\n";// cout<<lca(a,b)<<endl;}return 0;
}
相关文章:
P3398 仓鼠找 sugar
Portal. LCA。 询问树上两条路径是否有交点。 画图发现无非两种情况: 发现一条路径的起点和终点的 LCA 经过另一条路径,是两路径相交的充要条件。 考虑如何判断这个 LCA 在不在路径上。若 d ( s , LCA ) d ( LCA , t ) d ( s , t ) d(s,\text{LCA…...
C# 发送邮件
1.安装 NuGet 包 2.代码如下 SendMailUtil using MimeKit; using Srm.CMER.Application.Contracts.CmerInfo; namespace Srm.Mail { public class SendMailUtil { public async static Task<string> SendEmail(SendEmialDto sendEmialDto,List<strin…...
Zeal下载文档慢的问题
1. 安装Zeal 官方下载网站: https://zealdocs.org/ 2. 安装文档(在线安装方式)(下载速度非常慢) Tools - Docsets Available中下载安装对应的文档 3. 安装文档(离线安装方式) ①下载文档…...
HR模块开发(1):简单的开发流程和注意事项
HR模块开发 一、模块概述 人力资源管理解决方案关注3个领域:每位雇员都发展和维护着‘公司内’和‘公司外’的种种‘关系’。运用科技,强化这些关系,可以提高忠诚度和生产力,公司整体得到商业价值。 员工关系管理员工职业生命周期管理员工事务处理管理HR模块的基本知识和构…...
创建Vue实例
我们已经知道了Vue框架可以 基于数据帮助我们渲染出用户界面,那应该怎么做呢? 核心步骤(4步): 准备容器 引包(官网) — 开发版本/生产版本 创建Vue实例 new Vue() 指定配置项,渲…...
2024上海国际人工智能展(CSITF)以“技术,让生活更精彩”为核心理念,以“创新驱动发展,保护知识产权,促进技术贸易”为主题
2024上海国际人工智能展(CSITF) China(Shanghai)International Technology Fair 时间:2024年6月12-14日 地点:上海世博展览馆 主办单位 中华人民共和国商务部 中华人民共和国科学技术部 中华人民共和国国家知识产权局 上海市…...
Vue3使用Monaco-editor
Monaco-editor,一个vs code 编辑器,需要将其集成到项目。不说闲话了,直接上代码。 npm地址:https://www.npmjs.com/package/monaco-editor 中文文档:https://aydk.site/editor/ 安装: pnpm add monaco…...
java 根据ip获取到城市 GeoLite2-City.mmdb
本文可解决 根据ip定位获取不到问题,提供多种方式仅供参考: 1.选型 1.1 实现方式 Java可以实现IP地址解析和省市区信息查询,但是需要借助一些外部数据源或数据库来实现。常用的方法有以下几种: 1.1.1 本地文件解析 可以通过下…...
kaggle使用说明
kaggle kaggle使用参考1、kaggle目录2、kaggle上传本地文件后,如何不改代码就可运行3、已上传文件的修改3.1 重新上传3.2 重写文件 4、创建文件夹5、结果下载5.1 多文件:先打包再下载5.2 重定文件下载链接 kaggle使用参考 Kaggle 新手入门必看ÿ…...
BUUCTF FLAG 1
BUUCTF:https://buuoj.cn/challenges 题目描述: 注意:请将 hctf 替换为 flag 提交,格式 flag{} 密文: 下载附件,得到一张.png图片。 解题思路: 1、因为附件是一张图片,先放到StegSolve中&…...
万物皆可“云” 从杭州云栖大会看数智生活的未来
文章目录 前言一、云栖渐进:一个科技论坛的变迁与互联网历史互联网创新创业飞天进化飞天智能驱动数字中国 二、2023云栖大会:云计算人工智能 玩出科技跨界新花样大会亮点重磅嘉宾热门展览算力馆人工智能馆产业创新馆 总结 前言 10月31日,202…...
LeetCode1518 换水问题
题目描述 超市正在促销,你可以用 numExchange 个空水瓶从超市兑换一瓶水。最开始,你一共购入了 numBottles 瓶水。 如果喝掉了水瓶中的水,那么水瓶就会变成空的。 给你两个整数 numBottles 和 numExchange ,返回你 最多 可以喝…...
强大日志查看器,助力数据联动分析
前言 我们曾讨论过观测云查看器强大的查询筛选和搜索功能,能够帮助用户快速、精准地检索数据,定位故障问题(参见《如何使用查看器筛选、搜索功能进行数据定位?》)。除此之外,日志查看器不仅可以帮助我们收…...
HIBS一些简介
文章目录 距离发展:意义使用挑战安全IOT活动服务频带可行性频谱 距离 海拔约20KM的平流层中,国际电联无线电条例(RR)将HAPS定义为位于20-50公里高度和相对于地球的指定标称固定点的物体上的无线电台。 #高空平台作为IMT基站(HIB…...
OpenCV实现人脸关键点检测
目录 实现过程 1,代码解读 1.1 导入工具包 1.2导入所需图像,以及训练好的人脸预测模型 1.3 将 dlib 的关键点对象转换为 NumPy 数组,以便后续处理 1.4图像上可视化面部关键点 1.5# 读取输入数据,预处理 1.6进行人脸检测 1…...
300万美元!澳大利亚昆士兰州投资当地首家量子公司AQC
澳大利亚模拟量子电路公司(AQC)联合创始人 Tom Stace 教授和 Arkady Federov 副教授(图片来源:网络) 澳大利亚风险投资基金会Uniseed为澳大利亚昆士兰大学的两名教授提供了300万美元的资金,资助他们创办了…...
Android Studio打包AAR
注意 依赖的Android Studio版本为4.2.2 更高的Android Studio版本使用方法可能有所不同,gradle的版本和gradle plugins的版本都会影响使用方式。 基于此,本文只能作为参考,而不能作为唯一答案,如果要完全依赖本文,则…...
【Python基础知识四】控制语句
Python基础知识:控制语句 1 条件控制1.1 if语句1.2 match...case语句 2 循环语句2.1 for循环2.2 for...else语句2.3 while循环2.4 while 循环使用 else 语句2.5 无限循环2.6 break 和 continue 语句及循环中的 else 子句2.6.1 break语句2.6.2 continue语句 2.7 pass…...
Jmeter压测 —— 1秒发送1次请求
场景:有时候测试场景需要设置请求频率为一秒一次(或几秒一次)实现方法一:1、首先需要在线程组下设置循环次数(可以理解为请求的次数) 次数设置为请求300次,其中线程数跟时间自行设置 2、在设置…...
目标检测YOLO实战应用案例100讲-基于改进YOLOv4算法的自动驾驶场景 目标检测
目录 前言 国内外目标检测算法研究现状 传统目标检测算法的发展现状...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
