【*1900 图论+枚举思想】CF1328 E

这篇具有很好参考价值的文章主要介绍了【*1900 图论+枚举思想】CF1328 E。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Problem - E - Codeforces

题意:

【*1900 图论+枚举思想】CF1328 E,图论,图论

【*1900 图论+枚举思想】CF1328 E,图论,图论

【*1900 图论+枚举思想】CF1328 E,图论,图论

【*1900 图论+枚举思想】CF1328 E,图论,图论

思路:

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

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

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

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

为什么要加枚举的tag,因为可以发现满足条件的链的状态数很少,可以把这个作为切入点

【*1900 图论+枚举思想】CF1328 E,图论,图论

Code:文章来源地址https://www.toymoban.com/news/detail-621528.html

#include <bits/stdc++.h>

#define int long long

using 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的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【简单图论】CF898 div4 H

    Problem - H - Codeforces 题意: 思路: 手玩一下样例就能发现简单结论: v 离它所在的树枝的根的距离 m 离这个根的距离时是 YES 否则就是NO 实现就很简单,先去树上找环,然后找出这个根,分别给a 和 b BFS一遍,得出两个dis数组,比较一下即可 对于只有的环情况 和 m = v 的情况需

    2024年02月07日
    浏览(48)
  • CF1120 D. Power Tree 巧妙的图论转化

    传送门 [前题提要]:无 题目描述: 考虑对一个点的子树的所有 叶子节点 进行增减任意值.不难联想到对一个点的子树的 所有节点 增减任意值的做法.所以考虑使用类似于树链剖分的方式将树上修改化为链上区间修改. 考虑记录一个点的所有叶子节点,并且按照 d f s dfs df s 序将其

    2024年02月10日
    浏览(39)
  • 【图论经典题目讲解】CF715B - Complete The Graph

    D e s c r i p t i o n mathrm{Description} Description 给定一张 n n n 个点, m m m 条边的无向图,点的编号为 0 ∼ n − 1 0sim n-1 0 ∼ n − 1 ,对于每条边权为 0 0 0 的边赋一个不超过 1 0 18 10^{18} 1 0 18 的 正整数 权值,使得 S S S 到 T T T 的最短路长度为 L L L 。 S o l u t i o n mathrm{Solution} Solut

    2024年02月19日
    浏览(39)
  • 算法思想—枚举、递推、迭代、递归、分治、贪心、动态规划、回溯、模拟、分支定界

    算法思想 枚举(暴力算法) 枚举算法(暴力算法)是一种通过逐一尝试所有可能解来解决问题的算法。它的基本思想是将问题的所有可能答案一一列举出来,并根据一定的判断条件来确定哪些答案是合适的。这种算法通常使用循环来实现,因为需要尝试所有可能的情况。两

    2024年02月01日
    浏览(39)
  • 【图论经典题目讲解】CF786B - Legacy 一道线段树优化建图的经典题目

    D e s c r i p t i o n mathrm{Description} Description 给定 1 1 1 张 n n n 个点的有向图,初始没有边,接下来有 q q q 次操作,形式如下: 1 u v w 表示从 u u u 向 v v v 连接 1 1 1 条长度为 w w w 的有向边 2 u l r w 表示从 u u u 向 i i i ( i ∈ [ l , r ] iin [l,r] i ∈ [ l , r ] )连接 1 1 1 条长度为 w w w

    2024年02月20日
    浏览(89)
  • 【图论 状态压缩 枚举】2959. 关闭分部的可行集合数目

    图论 状态压缩 枚举 多源路径 一个公司在全国有 n 个分部,它们之间有的有道路连接。一开始,所有分部通过这些道路两两之间互相可以到达。 公司意识到在分部之间旅行花费了太多时间,所以它们决定关闭一些分部(也可能不关闭任何分部),同时保证剩下的分部之间两

    2024年04月13日
    浏览(35)
  • 【洛谷 P1328】[NOIP2014 提高组] 生活大爆炸版石头剪刀布 题解(模拟+向量)

    石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。 升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势: 斯波克:《星际迷航》主角之一。 蜥

    2024年02月09日
    浏览(39)
  • Linksys WRT1900ACS刷OpenWrt

    之前有台闲置的Linksys WRT1900ACS v2,可以拿来刷个OpenWrt做家用服务器。看了下OpenWrt官网对这台机器一直有支持,这里就选择OpenWrt官方固件了。各位可以根据喜好和硬件选择其他固件。 进入OpenWrt官网:https://openwrt.org/ 选择固件分支。我这里选择的是21.02.5(未选择最新的稳定分

    2024年02月11日
    浏览(63)
  • j1900软路由安装esxi6.7

    准备系统u盘这事就不说了。咱们从装系统开始说。这里有好几个大坑。 先说,我的软路由配置时J1900,4G内存、32G硬盘。买的配置比较低。这次说装esxi,这32G硬盘就不够看了,所以把机箱拆开看看能不能扩展一下存储。由于已经操作过了,没有留下图片,这里我就不上图了,

    2024年02月04日
    浏览(53)
  • AirSim编译不通过:C1900 “P1“ “P2“不匹配

    去年8月份在笔记本上玩过一阵子AirSim,今天刚好有空,就想拿出来再玩一会儿,结果发现死活编译通不过。即便是官方给的Block例程也编译不过,一直报以下错误:  C1900    “P1”(第“20220715”版)和“P2”(第“20210202”版)之间 Il 不匹配     说一下我的配置。我去年8月用的

    2024年02月12日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包