贪心/树形dp

思路:

因为如果红色节点的子树中如果有红色节点的话,那么该子树对其不会造成影响,不用考虑,因此我们在考虑每个红色节点时,不考虑其红色子树。那么如图,对每个红色节点答案有贡献的就是其所有非红色子节点的权值和。我们用dfs处理出每个红点的非红节点子树,然后枚举每个红色节点,然后在枚举该红色节点包括的所有结点中1的个数,保证1的个数不会超过2个,其他的结点权值为2.

代码:

int n;
string s;
vector<int>e[1000010], vc[1000010];
int ans[1000010];void dfs(int now,int md){vc[md].push_back(now);for(auto y : e[now]){if(s[y] == 'R')dfs(y, y);elsedfs(y,md);}
}void solve(){cin >> n;cin >> s;s = " " + s;for(int i = 2;i <= n;i ++){int x;cin >> x;e[x].push_back(i);}dfs(1,1);bool f = false;for(int i = 1;i <= n;i ++)ans[i] = 1;for(int i = 1;i <= n;i ++){if(s[i] != 'R')continue;int sz = vc[i].size();bool ok = false;for(int j = 0;j < 3;j ++){if(j > sz){break;}if((j + (sz - j) * 2) % 3 == 0){ok = true;for(int k = 0;k < j;k ++)ans[vc[i][k]] = 1;for(int k = j;k < sz;k ++)ans[vc[i][k]] = 2;break;}}if(!ok){f = true;break;}}if(f)cout << -1 << endl;elsefor(int i = 1;i <= n;i ++)cout << ans[i];
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/262571.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux——简单的Shell程序

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、Shell程序思路二、Shell代码展示 一、Shell程序思路 用下图的时间轴来表示事件的发生次序…

activeMq将mqtt发布订阅转成消息队列

1、activemq.xml置文件新增如下内容 2、mqttx测试发送&#xff1a; 主题&#xff08;配置的模糊匹配&#xff0c;为了并发&#xff09;&#xff1a;VirtualTopic/device/sendData/12312 3、mqtt接收的结果 4、程序处理 package comimport cn.hutool.core.date.DateUtil; imp…

(九)springmvc+mybatis+dubbo+zookeeper分布式架构 整合 - maven构建ant-framework核心代码Base封装

今天重点讲解的是ant-framework核心代码Base封装过程。 因为涉及到springmvc、mybatis的集成&#xff0c;为了使项目编码更简洁易用&#xff0c;这边将基础的BASE进行封装&#xff0c;其中包括&#xff1a;BaseBean、BaseDao、BaseService、CRUD的基础封装、分页组件的封装、m…

Spring6学习技术|Junit

学习材料 尚硅谷Spring零基础入门到进阶&#xff0c;一套搞定spring6全套视频教程&#xff08;源码级讲解&#xff09; Junit 背景 背景就是每次Test都要重复创建容器&#xff0c;获取对象。就是ApplicationContext和getBean两个语句。通过Spring整合Junit&#xff0c;可以…

开源分子对接程序rDock的安装及使用流程

欢迎浏览我的CSND博客&#xff01; Blockbuater_drug …点击进入 前言 本文介绍开源分子对接程序rDock在Linux Ubuntu 22.04系统上的conda安装、编译安装过程及程序使用流程。 一、rDock是什么&#xff1f; rDock来源 rDock是一个快速、多功能的开源对接程序&#xff0c;可用…

springmvc+mybatis+springboot航空飞机订票售票系统_f48cp

互联网发展的越来越快了&#xff0c;在当下社会节点&#xff0c;人们也开始越来越依赖互联网。通过互联网信息和数据&#xff0c;极大地满足用户要求[5]。飞机订票系统使用了B/S模式&#xff0c;并且不需要安装第三方插件&#xff0c;他们甚至能直接在电脑上随机随地实现飞机订…

【分享】关于MAX232一点心得

MAX232 DIP16封装现主要有这些型号&#xff1a;MAX232CPE、MAX232EPE。 下面对MAX232的型号标识进行解析&#xff1a; ①、MAX232后缀第一个字母&#xff0c;表示应用级别。带“C”&#xff1a;商业级&#xff1b;带“E”&#xff1a;工业级。 例&#xff1a;MAX232CPE&…

函数栈帧的创建及销毁(超详解)

目录 1.预备知识 1.1内存区的划分 1.2认识相关寄存器和汇编指令 1.2.1寄存器 1.2.2相关汇编指令 2.测试前 2.1测试代码及环境 2.2 main函数也是被其他函数调用的 3.函数栈帧的创建 4.进入函数内部 5.形参与实参 6.call/jump add函数 7.函数栈帧的销毁 7.1保存…

书生·浦语大模型实战营第二节课作业

使用 InternLM-Chat-7B 模型生成 300 字的小故事&#xff08;基础作业1&#xff09;。 熟悉 hugging face 下载功能&#xff0c;使用 huggingface_hub python 包&#xff0c;下载 InternLM-20B 的 config.json 文件到本地&#xff08;基础作业2&#xff09;。 下载过程 进阶…

linux下执行文件包含^M,将window文件格式内容转为linux格式

查看文件内容 cat -v jvm_options 报错信息 ./bin/install-plugin.sh: /bigdata/opt/s/seatunnelsgg/apache-seatunnel-2.3.4/mvnw: /bin/sh^M: bad interpreter: No such file or directory install connector : connector-selectdb-cloud安装工具 yum install -y dos2uni…

西门子S7-1500作为智能设备共享功能

本章节介绍了共享设备的功能&#xff0c;优势&#xff0c;使用要求&#xff0c;使用规则&#xff0c;如何将智能设备作为共享设备&#xff0c;实现一个智能设备同时与2个IO控制器进行通信的示例&#xff0c;以及常见问题。 一、共享设备功能概述 信号模块可以被不同的IO控制器…

「Kafka」监控、集成篇

Kafka-Eagle 监控 Kafka-Eagle 框架可以监控 Kafka 集群的整体运行情况&#xff0c;在生产环境中经常使用。 MySQL环境准备 Kafka-Eagle 的安装依赖于 MySQL&#xff0c;MySQL 主要用来存储可视化展示的数据。 安装步骤参考&#xff1a;P61 尚硅谷 kafka监控_MySQL环境准备 …

如何在同一个module里面集成多个数据库的多张表数据

确保本公司数据安全&#xff0c;通常对数据的管理采取很多措施进行隔离访问。 但是&#xff0c;Mendix应怎样访问散布于异地的多个数据库呢&#xff1f; 前几期我们介绍过出海跨境的大企业对于Mendix的技术、人才的诉求后&#xff0c;陆陆续续有其他客户希望更聚焦具体的实际场…

数据结构链表力扣例题AC(4)——代码以及思路记录

21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 AC struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 NULL){return list2;}if(list2 NULL){return l…

alibabacloud学习笔记06(小滴课堂)

讲Sentinel流量控制详细操作 基于并发线程进行限流配置实操 在浏览器打开快速刷新会报错 基于并发线程进行限流配置实操 讲解 微服务高可用利器Sentinel熔断降级规则 讲解服务调用常见的熔断状态和恢复 讲解服务调用熔断例子 我们写一个带异常的接口&#xff1a;

正交匹配追踪(Orthogonal Matching Pursuit, OMP)的MATLAB实现

压缩感知&#xff08;Compressed Sensing, CS&#xff09;是一种利用稀疏信号的先验知识&#xff0c;用远少于奈奎斯特采样定理要求的样本数目恢复整个信号的技术。正交匹配追踪&#xff08;Orthogonal Matching Pursuit, OMP&#xff09;是一种常见的贪婪算法&#xff08;Gree…

OCPP 1.6 接入实现文档

一、简介 OCPP&#xff08;Open Charge Point Protocol&#xff09;是一个开放的通信协议&#xff0c;用于充电站&#xff08;Charge Point&#xff09;与中央系统&#xff08;Central System&#xff0c;如充电站管理系统或服务提供商平台&#xff09;之间的通讯。本篇文档将…

谷歌搜索引擎关键词优化,竞价排名怎么做?大舍传媒

公司 大舍传媒成立于2005年&#xff0c;并从那时开始专注于谷歌搜索引擎优化&#xff08;SEO&#xff09;。如今&#xff0c;我们已经拥有了十八年的海外数字营销经验。我们为全球数千个国际知名品牌客户提供服务&#xff0c;是一家专注于技术的公司。 谷歌排名成果 在谷歌&…

Windows系统中定时执行python脚本

背景&#xff1a;本地Windows系统指定目录下会有文件的修改新增&#xff0c;这些变化的文件需要定时的被上传到git仓库中&#xff0c;这样不需要每次变更手动上传了。 首先编写一个检测文件夹下文件变化并且上传git仓库的python脚本(确保你已经在E:\edc_workspace\data_edc_et…

10.vue学习笔记(组件数据传递-props回调函数子传父+透传Attributes+插槽slot)

文章目录 1.组件数据传递2.透传Attributes&#xff08;了解&#xff09;禁用Attributes继承 3.插槽slot 1.组件数据传递 我们之前讲解过了组件之间的数据传递&#xff0c;props 和 自定义事件 两种方式 props&#xff1a;父传子 自定义事件&#xff1a;子传父 props通过额外方…