【*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 题意: 思路: 注意到题目的性质:满足条件的路径个数是极少的,因为每个点离路径的距离<1 先考虑一条链,那么直接就选最深那个点作为端点即可 为什么,因为我们需要遍历所有点…...
微信开发者工具 miniprogram_npm 未找到
背景 微信开发者工具中,打开集成了vant-weapp的项目,构建npm时,报错\miniprogram_npm\ 未找到。 问题 微信开发者工具,工具----->构建npm时,提示 message:发生错误 Error: D:\some\path\miniprogram…...
计算机视觉(三)未有深度学习之前
文章目录 图像分割基于阈值、基于边缘基于区域、基于图论 人脸检测Haar-like特征级联分类器 行人检测HOGSVMDPM 图像分割 把图像划分成若干互不相交的区域。经典的数字图像分割算法一般是基于灰度值的两个基本特征之一:不连续性和相似性。 基于阈值、基于边缘 基于…...
二十六、媒体查询2
目录: 媒体查询介绍网页常用分界点 一、媒体查询介绍 媒体特性: width 视口的宽度 height 视口的高度 一般设计的时候,高度不考虑,只考虑宽度 //当视口的宽度是500像素的时候,变颜色media (width: 500px) {body{background-colo…...
Themis 国库建设计划启动,开启去中心化新征程
在未来的金融领域,去中心化金融(DeFi)正在成为一种重要的趋势。在这股DeFi热潮中,作为Filecoin 生态下的一颗璀璨明珠,Themis 上线仅2个月,多项数据便稳居Filecoin-FVM榜首,TVL更是牢牢处于File…...
uni-app:模态框的实现(弹窗实现)
效果图 代码 标签 <template><view><!-- 按钮用于触发模态框的显示 --><button click"showModal true">显示模态框</button><!-- 模态框组件 --><view class"modal" v-if"showModal"><view cla…...
第九章:stack类
系列文章目录 文章目录 系列文章目录前言stack的介绍stack的使用成员函数使用stack 总结 前言 stack是容器适配器,底层封装了STL容器。 stack的介绍 stack的文档介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除…...
FSM:Full Surround Monodepth from Multiple Cameras
参考代码:None 介绍 深度估计任务作为基础环境感知任务,在基础上构建的3D感知才能更加准确,并且泛化能力更强。单目的自监督深度估计已经有MonoDepth、ManyDepth这些经典深度估计模型了,而这篇文章是对多目自监督深度估计进行探…...
idea 安装 插件jrebel 报错LS client not configured.
这个报错找了好久,有博主说版本不对,我脑子没反应过来以为是随便换一个低版本的就行,没想到只能是2022.4.1 这个版本才行 一定要用jrebel 2022.4.1的插件版本!!!!! 插件下载地址&…...
Raki的读paper小记:RWKV: Reinventing RNNs for the Transformer Era
Abstract&Introduction&Related Work 研究任务 基础模型架构已有方法和相关工作 RNN,CNN,Transformer稀疏注意力(Beltagy等人,2020年;Kitaev等人,2020年;Guo等人,2022年&am…...
PaddleOCR #PP-OCR常见异常扫雷
异常一:ModuleNotFoundError: No module named ‘tools.infer’ 实验案例: PaddleOCR #使用PaddleOCR进行光学字符识别(PP-OCR文本检测识别) 参考代码: 图片文本检测实验时,运行代码出现异常:M…...
Qt加载字体文件
本文记录如何使用 Qt 加载外部字体文件,并遍历字体名称和样式名称。 bool LoadFont(const QString& fontPath) {const int fontId QFontDatabase::addApplicationFont(fontPath);if (fontId -1) {return false;}// 遍历字体名和样式名 #if QT_VERSION > QT…...
3ds MAX绘制简单动画
建立一个长方体和茶壶: 在界面右下角点击时间配置: 这是动画制作的必要步骤 选择【自动】,接下来,我们只要在对应的帧改变窗口中图形的位置,就能自动记录该时刻的模样 这就意味着,我们通过电脑记录某几个…...
页面访问控制远程仓库
页面访问权限控制 什么是jwt身份认证 在前后端分离模式的开发中,服务器如何知道来访者的身份呢? 在登录后,服务器会响应给用户一个 令牌 (token)令牌中会包括该用户的id等唯一标识浏览器收到令牌后,自己…...
小程序 user agent stylesheet 覆盖了page下wxss背景色
如下图: login页面的page下的背景色,被:user agent stylesheet覆盖。 分析与解决: 1、user agent stylesheet是浏览器默认样式表,是浏览器默认样式。 2、不同浏览器的默认样式不同个,甚至同种浏览器不同版…...
Vue.js高阶学习和常用知识(二)
目录 1. Vue 实例2. 组件3. 指令4. 计算属性5. 监听器6. 生命周期钩子 Vue.js 是一个流行的 Web 前端框架,它由 Evan You 于 2014 年创建。Vue.js 的设计目标是简单、灵活和易于使用,同时具有高性能和可扩展性。 Vue.js 基于组件化的思想,将页…...
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…...
云原生训练营课程大纲
第一部分:Go 语****言基础 模块一:Go 语言特性 教学目标: 理解 Go 语言基本语法 理解 Go 语言常用数据类型 理解 Go 语言常用小技巧 深入理解 Go 语言的多线程编程 针对的用户痛点: 云原生从业者因为未熟练掌握 Go 语言&#…...
【Ajax】笔记-同源策略
同源策略(Same-Origin Policy),是浏览器的一种安全策略 同源(即url相同):协议、域名、端口号 必须完全相同。(请求是来自同一个服务) 跨域:违背了同源策略,即跨域。 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.效果展示…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
