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

【*1900 图论】CF1328 E

Problem - E - Codeforces

题意:

思路:

注意到题目的性质:满足条件的路径个数是极少的,因为每个点离路径的距离<=1

先考虑一条链,那么直接就选最深那个点作为端点即可

为什么,因为我们需要遍历所有点的父亲

推广到树,也是要遍历所有点的父亲

Code:

#include <bits/stdc++.h>#define int long longusing namespace std;const int mxn=2e5+10;
const int mod=1e9+7;vector<int> G[mxn];int N,M,K,u,v,x;
int idx=0;
int dep[mxn],In[mxn],sz[mxn],F[mxn];void dfs(int u,int fa){sz[u]=1;F[u]=fa;dep[u]=dep[fa]+1;In[u]=++idx;for(auto v:G[u]){if(v==fa) continue;dfs(v,u);sz[u]+=sz[v];}
}
bool cmp(int x,int y){return dep[x]<dep[y];
}
bool check(int u,int v){return In[v]>=In[u]&&In[v]<=In[u]+sz[u]-1;
}
void init(){for(int i=0;i<=N;i++){dep[i]=In[i]=sz[i]=F[i]=0;G[i].clear();}
}
void solve(){cin>>N>>M;init();for(int i=1;i<=N-1;i++){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}dfs(1,0);F[1]=1;while(M--){cin>>K;vector<int> V;for(int i=1;i<=K;i++){cin>>x;V.push_back(F[x]);}//for(int i=0;i<V.size();i++) cout<<V[i]<<" \n"[i==V.size()-1];sort(V.begin(),V.end(),cmp);int ok=1;for(int i=1;i<V.size();i++){if(!check(V[i-1],V[i])){ok=0;break;} }if(ok) cout<<"YES"<<'\n';else cout<<"NO"<<'\n';}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}

相关文章:

【*1900 图论】CF1328 E

Problem - E - Codeforces 题意&#xff1a; 思路&#xff1a; 注意到题目的性质&#xff1a;满足条件的路径个数是极少的&#xff0c;因为每个点离路径的距离<1 先考虑一条链&#xff0c;那么直接就选最深那个点作为端点即可 为什么&#xff0c;因为我们需要遍历所有点…...

微信开发者工具 miniprogram_npm 未找到

背景 微信开发者工具中&#xff0c;打开集成了vant-weapp的项目&#xff0c;构建npm时&#xff0c;报错\miniprogram_npm\ 未找到。 问题 微信开发者工具&#xff0c;工具----->构建npm时&#xff0c;提示 message&#xff1a;发生错误 Error: D:\some\path\miniprogram…...

计算机视觉(三)未有深度学习之前

文章目录 图像分割基于阈值、基于边缘基于区域、基于图论 人脸检测Haar-like特征级联分类器 行人检测HOGSVMDPM 图像分割 把图像划分成若干互不相交的区域。经典的数字图像分割算法一般是基于灰度值的两个基本特征之一&#xff1a;不连续性和相似性。 基于阈值、基于边缘 基于…...

二十六、媒体查询2

目录&#xff1a; 媒体查询介绍网页常用分界点 一、媒体查询介绍 媒体特性&#xff1a; width 视口的宽度 height 视口的高度 一般设计的时候&#xff0c;高度不考虑&#xff0c;只考虑宽度 //当视口的宽度是500像素的时候,变颜色media (width: 500px) {body{background-colo…...

Themis 国库建设计划启动,开启去中心化新征程

在未来的金融领域&#xff0c;去中心化金融&#xff08;DeFi&#xff09;正在成为一种重要的趋势。在这股DeFi热潮中&#xff0c;作为Filecoin 生态下的一颗璀璨明珠&#xff0c;Themis 上线仅2个月&#xff0c;多项数据便稳居Filecoin-FVM榜首&#xff0c;TVL更是牢牢处于File…...

uni-app:模态框的实现(弹窗实现)

效果图 代码 标签 <template><view><!-- 按钮用于触发模态框的显示 --><button click"showModal true">显示模态框</button><!-- 模态框组件 --><view class"modal" v-if"showModal"><view cla…...

第九章:stack类

系列文章目录 文章目录 系列文章目录前言stack的介绍stack的使用成员函数使用stack 总结 前言 stack是容器适配器&#xff0c;底层封装了STL容器。 stack的介绍 stack的文档介绍 stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&#xff0c;其删除…...

FSM:Full Surround Monodepth from Multiple Cameras

参考代码&#xff1a;None 介绍 深度估计任务作为基础环境感知任务&#xff0c;在基础上构建的3D感知才能更加准确&#xff0c;并且泛化能力更强。单目的自监督深度估计已经有MonoDepth、ManyDepth这些经典深度估计模型了&#xff0c;而这篇文章是对多目自监督深度估计进行探…...

idea 安装 插件jrebel 报错LS client not configured.

这个报错找了好久&#xff0c;有博主说版本不对&#xff0c;我脑子没反应过来以为是随便换一个低版本的就行&#xff0c;没想到只能是2022.4.1 这个版本才行 一定要用jrebel 2022.4.1的插件版本&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 插件下载地址&…...

Raki的读paper小记:RWKV: Reinventing RNNs for the Transformer Era

Abstract&Introduction&Related Work 研究任务 基础模型架构已有方法和相关工作 RNN&#xff0c;CNN&#xff0c;Transformer稀疏注意力&#xff08;Beltagy等人&#xff0c;2020年&#xff1b;Kitaev等人&#xff0c;2020年&#xff1b;Guo等人&#xff0c;2022年&am…...

PaddleOCR #PP-OCR常见异常扫雷

异常一&#xff1a;ModuleNotFoundError: No module named ‘tools.infer’ 实验案例&#xff1a; PaddleOCR #使用PaddleOCR进行光学字符识别&#xff08;PP-OCR文本检测识别&#xff09; 参考代码&#xff1a; 图片文本检测实验时&#xff0c;运行代码出现异常&#xff1a;M…...

Qt加载字体文件

本文记录如何使用 Qt 加载外部字体文件&#xff0c;并遍历字体名称和样式名称。 bool LoadFont(const QString& fontPath) {const int fontId QFontDatabase::addApplicationFont(fontPath);if (fontId -1) {return false;}// 遍历字体名和样式名 #if QT_VERSION > QT…...

3ds MAX绘制简单动画

建立一个长方体和茶壶&#xff1a; 在界面右下角点击时间配置&#xff1a; 这是动画制作的必要步骤 选择【自动】&#xff0c;接下来&#xff0c;我们只要在对应的帧改变窗口中图形的位置&#xff0c;就能自动记录该时刻的模样 这就意味着&#xff0c;我们通过电脑记录某几个…...

页面访问控制远程仓库

页面访问权限控制 什么是jwt身份认证 在前后端分离模式的开发中&#xff0c;服务器如何知道来访者的身份呢&#xff1f; 在登录后&#xff0c;服务器会响应给用户一个 令牌 &#xff08;token&#xff09;令牌中会包括该用户的id等唯一标识浏览器收到令牌后&#xff0c;自己…...

小程序 user agent stylesheet 覆盖了page下wxss背景色

如下图&#xff1a; login页面的page下的背景色&#xff0c;被&#xff1a;user agent stylesheet覆盖。 分析与解决&#xff1a; 1、user agent stylesheet是浏览器默认样式表&#xff0c;是浏览器默认样式。 2、不同浏览器的默认样式不同个&#xff0c;甚至同种浏览器不同版…...

Vue.js高阶学习和常用知识(二)

目录 1. Vue 实例2. 组件3. 指令4. 计算属性5. 监听器6. 生命周期钩子 Vue.js 是一个流行的 Web 前端框架&#xff0c;它由 Evan You 于 2014 年创建。Vue.js 的设计目标是简单、灵活和易于使用&#xff0c;同时具有高性能和可扩展性。 Vue.js 基于组件化的思想&#xff0c;将页…...

html实现蜂窝菜单

效果图 CSS样式 keyframes _fade-in_mkmxd_1 {0% {filter: blur(20px);opacity: 0}to {filter: none;opacity: 1} } keyframes _drop-in_mkmxd_1 {0% {transform: var(--transform) translateY(-100px) translateZ(400px)}to {transform: var(--transform)} } ._examples_mkmx…...

云原生训练营课程大纲

第一部分&#xff1a;Go 语****言基础 模块一&#xff1a;Go 语言特性 教学目标&#xff1a; 理解 Go 语言基本语法 理解 Go 语言常用数据类型 理解 Go 语言常用小技巧 深入理解 Go 语言的多线程编程 针对的用户痛点&#xff1a; 云原生从业者因为未熟练掌握 Go 语言&#…...

【Ajax】笔记-同源策略

同源策略(Same-Origin Policy)&#xff0c;是浏览器的一种安全策略 同源&#xff08;即url相同&#xff09;&#xff1a;协议、域名、端口号 必须完全相同。&#xff08;请求是来自同一个服务&#xff09; 跨域&#xff1a;违背了同源策略&#xff0c;即跨域。 ajax请求是遵循…...

Java使用FFmpeg实现mp4转m3u8

Java使用FFmpeg实现mp4转m3u8 前言FFmpegM3U8 一、需求及思路分析二、安装FFmpeg1.windows下安装FFmpeg2.linux下安装FFmpegUbuntuCentOS 三、代码实现1.引入依赖2.修改配置文件3.工具类4.Controlle调用5.Url转换MultipartFile的工具类 四、播放测试1.html2.nginx配置3.效果展示…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

代理服务器-LVS的3种模式与调度算法

作者介绍&#xff1a;简历上没有一个精通的运维工程师。请点击上方的蓝色《运维小路》关注我&#xff0c;下面的思维导图也是预计更新的内容和当前进度(不定时更新)。 我们上一章介绍了Web服务器&#xff0c;其中以Nginx为主&#xff0c;本章我们来讲解几个代理软件&#xff1a…...

数据库管理与高可用-MySQL故障排查与生产环境优化

目录 #1.1MySQL单案例故障排查 1.1.1MySQL常见的故障排查 1.1.2MySQL主从故障排查 #2.1MySQL优化 2.1.1硬件方面的优化 2.1.2进程方面的优化 #3.1MySQL存储引擎 3.1.1 MyISAM存储引擎 3.1.2 InnoDB存储引擎 1.1MySQL单案例故障排查 1.1.1MySQL常见的故障排查 &#xff08;1&…...

【免杀】C2免杀技术(十五)shellcode混淆uuid/ipv6/mac

针对 shellcode 混淆(Shellcode Obfuscation) 的实战手段还有很多,如下表所示: 类型举例目的编码 / 加密XOR、AES、RC4、Base64、Poly1305、UUID、IP/MAC改变字节特征,避开静态签名或 YARA结构伪装PE Stub、GIF/PNG 嵌入、RTF OLE、UUID、IP/MAC看起来像合法文件/数据,弱…...