Codeforces Round 303 (Div. 2)C. Kefa and Park(DFS、实现)

这篇具有很好参考价值的文章主要介绍了Codeforces Round 303 (Div. 2)C. Kefa and Park(DFS、实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题面

Codeforces Round 303 (Div. 2)C. Kefa and Park(DFS、实现),codeforces,算法,c++,mybatis,django,java,spring boot,spring

链接

C. Kefa and Park

题意

求叶节点数量,叶节点满足,从根节点到叶节点的路径上最长连续1的长度小于m

题解

这道题目主要是实现,当不满足条件时直接返回。
到达叶节点后统计答案,用vector存图的话,无向图时,叶节点的边只有一条,也就是 g [ i ] . s i z e ( ) = = 1 g[i].size()==1 g[i].size()==1而不是0
需要特判是一条链的情况,一条链的话根节点的 g [ i ] . s i z e ( ) = = 1 g[i].size()==1 g[i].size()==1也成立

代码

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;
const int N=1e5+10;
vector<int>g[N];
int a[N],ans,n,m;

void dfs(int u,int fa,int sum,int maxx){
	if(maxx>m){	
		return;
	}
	//统计答案
	if(g[u].size()==1&&max(maxx,sum+a[u])<=m&&u!=1){
//		cout<<"----------"<<u<<endl;
		ans++;
		return;
	}
	for(auto y:g[u]){
		if(y==fa)	continue;
		if(a[u]==1){
			if(a[fa]==1){
				dfs(y,u,sum+1,max(maxx,sum+1));
			}else{
				dfs(y,u,1,max(maxx,1*1ll));
			}
		}else{
			dfs(y,u,0,maxx);
		}
	}
}


void solve()
{
	cin>>n>>m;
	rep(i,1,n){
		cin>>a[i];
	}
	rep(i,1,n-1){
		int u,v;cin>>v>>u;
		g[u].pb(v);
		g[v].pb(u);
	}
	//当前结点、根节点,目前连续猫数。
	dfs(1,0,0,0);
	cout<<ans<<endl;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

总结

这道题目主要是dfs的实现,树的遍历,以及在遍历过程中维护相关信息。同时需要考虑一些细节,特殊情况比如树是一条链。文章来源地址https://www.toymoban.com/news/detail-825824.html

到了这里,关于Codeforces Round 303 (Div. 2)C. Kefa and Park(DFS、实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C. Salyg1n and the MEX Game Codeforces Round 897 (Div. 2)

    Problem - C - Codeforces 题目大意:有一个所有数互不相同的长度为n的数组n,A先手,可以向数组中假如一个没有的数x,B可以从数组中移除一个x的数,目标是使数组最终的MEX最小,扮演A进行操作,使数组最终的MEX最大 1=n=1e5;最大回合数为n 思路:我们要让当前数组的MEX增大,必

    2024年02月07日
    浏览(32)
  • Codeforces Round 920 (Div. 3)

    Codeforces Round 920 (Div. 3) 题意:随机给出正方形在平面坐标系上的四个顶点的坐标,求正方形的面积,正方形边与xy轴平行。 思路:因为正方形与坐标轴平行,所以找出相同的两x或y坐标即可找到一条边的长度,平方就是面积,注意结果返回整型。 AC code: 题意:给出两个01字符

    2024年01月17日
    浏览(67)
  • Codeforces Round 882 (Div. 2)

    目录 A. The Man who became a God  题目分析: B. Hamon Odyssey 题目分析: C. Vampiric Powers, anyone? 题目分析:  n个人分成k组,每一组的力量都是 这样的,那么如果分成k组那么就会有k-1个力量不被统计,将力量总和减去前k-1个最大的力量就是最小的结果   将数组分组,每个组内进行按位与

    2024年02月05日
    浏览(50)
  • Codeforces Round 912 (Div. 2)

    大等于2依据冒泡排序即可排序,因此判断下1即可 对每一个数字找哪一位肯定为0填0其他的填1 从后往前考虑加到当前集合或新立一个集合 从最高位开始考虑能否为1,计算能否时每个数当前位为1

    2024年02月04日
    浏览(45)
  • Codeforces Round 881 (Div. 3)

    给定一个数组,给每个元素涂色。求最大的代价。 代价为每个颜色的代价和。 每个颜色的代价为涂了该颜色的元素的极差。 因为是极差,每个元素要么对答案有正的贡献,要么有负的贡献,要么无贡献。且正负贡献的个数要相同。 因为要最大值,自然就是想有正贡献的是最

    2024年02月09日
    浏览(44)
  • Codeforces Round 867 (Div. 3)

    从所有a[i]+i-1=t的选择种取个max即可 实际上就是取同符号乘积的最大值 找规律,发现结果与边长n的关系是:res = n * (n + 3) - (n - 2) ①当n为奇数时,除了1其他均无解 ②当n为偶数时,我们可以构造一个形如n,1,n - 2,3,...的数列 首先我们可以发现n必定出现在起始位置。如果n不在起

    2024年02月02日
    浏览(49)
  • Codeforces Round 874 (Div. 3)

    用最少的长度为2的字符串按一定规则拼出s。规则是:前一个字符串的尾与后一个字符串的首相同。 统计s中长度为2的不同字符串数量。 给定数组a[n]和b[n],重排b后,令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。 将a和b分别按从小到大的顺序匹配便是最优的,一定能满足

    2024年02月05日
    浏览(38)
  • Codeforces Round 894 (Div. 3)

    签到题 a数组里,大于等于前一个值的a[i]会被写到b里。直接遍历b,如果b[i]比前一个小就在它前面插一个相等的值 计算反过来的长度,判断是否相等就行 对于没有重复口味的集合,能选出的方案是n*(n-1)/2 (从n个里面选2个的组合数)。二分找出需要多少不同口味的冰淇淋,

    2024年02月11日
    浏览(45)
  • Codeforces Round 926 (Div. 2)

    类似于倍投法,就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制,不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111,前3把一直输,但是只要第4把赢,就一定可以增加 1

    2024年02月20日
    浏览(45)
  • Codeforces Round 868 Div 2

    要求构造一个仅包含 (1) 和 (-1) 的长度为 (n) 的数组 (a) ,使得存在 (k) 个下标对 ((i, j), i j) 满足 (a_i times a_j = 1) 。 当有 (x) 个 (1) , (y) 个 (-1) 时,其满足条件的下标对数量为 (frac{x (x - 1)}{2} + frac{y (y - 1)}{2}) 。 由于 (n) 只有 (100) ,直接枚举 (x) 即可。

    2024年02月01日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包