首页 > 其他分享 >P10298 [CCC 2024 S4] Painting Roads

P10298 [CCC 2024 S4] Painting Roads

时间:2024-05-24 21:56:24浏览次数:27  
标签:P10298 S4 2024 交替 涂色 lca CCC

原题链接

题解

由易到难,先不考虑交替的事情,既然要尽量少的涂色,那么我最少要涂几条颜色的边?(由于图不一定联通,这里先考虑连通图的情况)

如果一条边处于一个环内,那么这个边就可以不涂色。
所以只要有环我就可以选择一条边不涂色,那么到最后,涂色的边构成一棵树

接下来考虑这颗树能否实现红蓝交替
要满足红蓝交替,则要满足对于任意两点 \(u,v\),\(u \to lca(u,v)\),\(v \to lca(u,v)\) 的边是交替的,且 \(lca(u,v)\) 通向两点的第一条边颜色不同
满足前半个条件很简单,按深度奇偶性涂色
一条灰色边对应一个环,无向图dfs生成树一定满足上述限制,即生成树中上述情况不可能存在

code


标签:P10298,S4,2024,交替,涂色,lca,CCC
From: https://www.cnblogs.com/pure4knowledge/p/18211754

相关文章

  • mathtype7最新产品密钥2024免费激活码
     MathType2024,作为最新的专业数学公式编辑神器,以其强大的功能和用户友好的界面,正在重新定义我们编写和分享复杂数学公式的方式。我们需要了解什么是MathType。MathType是一款专业的数学公式编辑软件,它可以帮助教师、学生和科研人员快速创建复杂的数学公式,并可以轻松插入到各......
  • 日常总结(10):2024年05月24日
    日常总结几天没总结了,最近考了几次试。05.0960ptsrk505.1145ptsrk5T1没开longlong同时100pts05.14200ptsrk3最后一题暴力写挂少20pts痛失rk105.1672ptsrk6这一场非常的拉,前两题思路都挂掉05.18220ptsrk3第一题没转double失40pts痛失rk105.21300ptsr......
  • CCF-CSP认证 2024年3月 4.化学方程式配平
    题解:首先完成数据的读入,然后高斯消元求秩按题意解即可#pragmaGCCoptimize(2,3,"Ofast","inline")#include<bits/stdc++.h>usingnamespacestd;constintmaxn=100;usingmatrix=double[maxn][maxn];usingvect=array<double,maxn>;constdoub......
  • 【专题】2024体验赋能企业出海白皮书报告合集PDF分享(附原数据表)
    原文链接:https://tecdat.cn/?p=36251原文出处:拓端数据部落公众号在全球化浪潮日益汹涌的商业环境中,出海企业正面临着前所未有的机遇与严峻挑战。面对产品和服务日益同质化的问题,企业如何在国际市场上独树一帜?答案并非仅仅依赖于创新和成本控制。如今,以“体验+品牌”为核心的战......
  • 【专题】2024抖音春日热点报告-餐饮篇报告合集PDF分享(附原数据表)
    原文链接:https://tecdat.cn/?p=35422原文出处:拓端数据部落公众号2023年,中国经济表现稳健,零售消费稳定增长,尤其国内旅游市场迅速回暖,人们出行频率回升,酒店、餐饮和旅游服务的消费需求稳步攀升,为相关行业复苏提供了强大动力。据文化和旅游部数据显示,全年国内旅游总人次和收入均实......
  • Camtasia Studio2024神器级别的电脑录屏编辑软件
    在数字化时代的今天,视频已经成为了人们获取信息和交流的重要方式。而在这个过程中,屏幕录制和视频编辑软件的作用不可忽视。CamtasiaStudio2024就是一款功能强大的屏幕录制和视频编辑软件,它可以帮助用户轻松地创建专业级别的视频内容。我们来了解一下什么是屏幕录制。屏幕录......
  • 2024“中国电机工程学会杯”数学建模大赛A题思路和代码分享
    A题:园区微电网风光储协调优化配置        这个题目整体就是一个优化问题,可以采用Matlab+Yalmip+Gurobi求解器进行求解,持续更新中,敬请关注!!        园区微电网由风光发电和主电网联合为负荷供电,为了尽量提高风光电量的负荷占比,需配置较高比例的风光发电装机......
  • 2024年旗舰手机和中端机的区别
    两款手机都是o家的findx7ultra二手的16+256g4500元realmeneo6se全新16+256g2150元(使用一个月降价400元)先说结论哇,体验已经很接近了,cpu性能瓶颈,对于日常使用来说已经区别不大最大的区别在以下几个方面:旗舰优点:拍照:不用说了,看看findx7硕大的摄像模组都知道,用真我的拍照......
  • 前端发展历史与未来展望(2024)
    前端开发技术的发展可以分为以下几个阶段:一.农业时代静态页面:最早期的Web界面,主要使用HTML和少量JavaScript。带有简单逻辑的界面:引入了JavaScript用于基本的客户端操作。混合编程:结合服务端技术(如CGI、ASP、JSP、PHP)实现更复杂的功能。组件化萌芽:服务端和客户端组件化(如AS......
  • 【热门会议|火热征稿】2024年语言、艺术与文化交流国际会议(LACE 2024)
    2024年语言、艺术与文化交流国际会议(LACE2024)2024InternationalConferenceonLanguage,Art,andCulturalExchange【重要信息】大会地点:成都大会官网:http://www.iaclace.com投稿邮箱:[email protected]【注意:将稿件Word+PDF上传至邮箱,邮件正文请备注“LACE2024+......