(AcWing)没有上司的舞会

news/2024/3/4 9:59:03

Ural 大学有 NN 名职员,编号为 1∼N。

他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。

每个职员有一个快乐指数,用整数 Hi 给出,其中 1≤i≤N。

现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。

在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。

输入格式

第一行一个整数 N。

接下来 N 行,第 i 行表示 i 号职员的快乐指数 Hi。

接下来 N−1 行,每行输入一对整数 L,K,表示 K 是 L 的直接上司。(注意一下,后一个数是前一个数的父节点,不要搞反)。

输出格式

输出最大的快乐指数。

数据范围

1≤N≤6000,
−128≤Hi≤127

输入样例:

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例:

5
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N = 6010;//定义邻接表
int h[N];   //存储所有的表头
int e[N];   //存所有的边
int ne[N];  //存每个节点的下一个值为多少
int idx;    //表示当前使用到的点,可以理解为该点的坐标int happy[N];//存储每个员工的开心值
bool father[N];//判断该点有没有父节点int f[N][2]; 
//f[u][0]:所有从以u为根的子树中选,并且不选u这个点的方案
//f[u][1]:所有从以u为根的子树中选,并且选u这个点的方案void add(int a,int b) 
{e[idx] = b;        //生成一个新节点,代表坐标为idx的点的值为bne[idx] = h[a];    //插入到表头,新节点的下一个节点为原来a这条链表的第一个节点h[a] = idx;        //表头的下一个节点为新节点的坐标idx++;             //更新坐标idx
}void dfs(int u)
{f[u][1] = happy[u]; //选u这个点的话就要把该点的开心值加上for(int i=h[u];i!=-1;i = ne[i]) //遍历u所有的子节点,{int j = e[i];dfs(j);                     //递归处理子节点f[u][1] += f[j][0];f[u][0] += max(f[j][0],f[j][1]);}
}int main()
{int n;cin>>n;memset(h,-1,sizeof h);   //初始化所有表头,-1表示空表头for(int i=1;i<=n;i++) cin>>happy[i]; //读入每个员工的开心值for(int i=1;i<=n-1;i++){   //读入边,k是l的直接上司可以理解为k是l的父节点,l是k的子树int l,k;cin>>l>>k;father[l] = true;   //l已有父节点add(k,l);}int root = 1; while(father[root]) root++;dfs(root);cout<<max(f[root][0],f[root][1])<<endl;
}

 

 


http://www.ppmy.cn/news/1054490.html

相关文章

PDF中的表格怎么转换为Excel?这两个工具一定得收藏!

PDF是一种常见的文件格式&#xff0c;它可以保持文件的原始样式和内容&#xff0c;但是也有一些缺点&#xff0c;比如不易编辑和处理数据。如果你想要将PDF中的表格或数据导出到Excel中&#xff0c;以便进行分析、计算或制作图表&#xff0c;那么你可能需要一个专业的PDF转Exce…

湖北咸宁农业三维扫描数字化农业3d打印制造应用-CASAIM中科广电

农业是人类衣食之源、生存之本&#xff0c;是一切生产的首要条件&#xff0c;CASAIM在农业三维扫描和3d打印应用上有丰富经验。 1.三维扫描技术在农业领域的应用 CASAIM三维扫描是集光学、机电和计算机技术于一体的高新无损检测技术&#xff0c;能够对实物的空间外形、结构乃…

微信小程序教学系列(4)

微信小程序教学系列 第四章&#xff1a;小程序优化与调试 1. 性能优化技巧 在开发微信小程序时&#xff0c;我们可以采取一些性能优化技巧&#xff0c;以提升小程序的性能表现和用户体验。以下是一些常用的性能优化技巧&#xff1a; 减少网络请求&#xff1a;尽量合并网络请…

window10安装并使用oracle

1、现在oracle19c或者21c&#xff0c;下载链接如下 Database Software Downloads | Oracle 中国 2、安装好之后&#xff0c; 2.1PL/SQL连接方式 命令窗口输入sqlplus conn as sysdba 2.2DBeaver连接 输入IP、 端口默认1521 数据库默认是ORCL 用户名是system 角色是N…

DHCP脚本,修改网卡信息脚本,编译安装nginx脚本,pxe脚本

目录 DHCP脚本 修改网卡信息脚本 编译安装nginx pxe批量装机脚本 DHCP脚本 仅供参考&#xff08;不保证谁都可以使用&#xff09; #!/bin/bash pzwj () { read -p "输入网段:" NET #输入网段&#xff0c;ip去掉主机位 read -p "输入子网掩码:" MASK …

批量将excel文件按照分类生成多个excel文件

要批量将Excel文件按照分类生成多个Excel文件&#xff0c;文件名为分类名&#xff0c;可以使用Python中的pandas库来实现。下面是示例代码&#xff1a; import pandas as pd import os def split_excel_by_category(file_path, category_column, output_folder): # 读取Ex…

【JAVA基础】 IO详解

【JAVA基础】 IO详解 文章目录 【JAVA基础】 IO详解一、概述二、IO流的作用三、IO流的使用场景四、IO流的分类4.1 传输数据的单位分&#xff1a;4.2 数据传输的方向分&#xff1a;4.3 流的角色的不同分&#xff1a; 五、IO流体系六、字节输入流InputStream七、字节输出流 Outpu…

奇迹MU服务器如何选择配置?奇迹MU服务器租用

不同的服务器&#xff0c;根据其特点与性能适用于不同的应用场景&#xff0c;为了让你们更好的理解&#xff0c;我们对服务器进行了分类归纳&#xff0c;结合了服务器不同的特点以及价位进行一个区分&#xff0c;帮助我们更好的选择合适的服务器配置。 VPS服务器 VPS服务器又…

Linux socket网络编程

一、主机字节序列和网络字节序列 主机字节序列分为大端字节序列和小端字节序列&#xff0c;不同的主机采用的字节序列可能不同。大端字节序列是指一个整数的高位字节存储在内存的低地址处&#xff0c;低位字节存储在内存的高地址处。小端字节序列是指整数的高位字节存储在内存…

k8s发布应用

前言 首先以SpringBoot应用为例介绍一下k8s的发布步骤。 1.从代码仓库下载代码&#xff0c;比如GitLab&#xff1b; 2.接着是进行打包&#xff0c;比如使用Maven&#xff1b; 3.编写Dockerfile文件&#xff0c;把步骤2产生的包制作成镜像&#xff1b; 4.上传步骤3的镜像到…

相机设置报错记录

Camera->SetPosition(0.0, -980, 0.0);Camera->SetFocalPoint(0.0, 0.0, 0.0);Camera->SetViewUp(0.0, 1.0, 0.0);上述代码出现错误提示Resetting view-up since view plane normal is parallel&#xff0c;这个时候是viewup方向与投影方向平行了&#xff0c;而出现的…

HTML 和 CSS 来实现毛玻璃效果(Glassmorphism)

毛玻璃效果简介 它的主要特征就是半透明的背景&#xff0c;以及阴影和边框。 同时还要为背景加上模糊效果&#xff0c;使得背景之后的元素根据自身内容产生漂亮的“变形”效果&#xff0c;示例&#xff1a; 代码实现 首先&#xff0c;创建一个 HTML 文件&#xff0c;写入如下…

Kubernetes(K8S)简介

Kubernetes (K8S) 是什么 它是一个为 容器化 应用提供集群部署和管理的开源工具&#xff0c;由 Google 开发。Kubernetes 这个名字源于希腊语&#xff0c;意为“舵手”或“飞行员”。k8s 这个缩写是因为 k 和 s 之间有八个字符的关系。 Google 在 2014 年开源了 Kubernetes 项…

工业生产全面感知!工业感知云来了

面向工业企业数字化转型需求&#xff0c;天翼物联基于感知云平台创新能力和5G工业物联数采能力&#xff0c;为客户提供工业感知云服务&#xff0c;包括工业泛协议接入、感知云工业超轻数采平台、工业感知数据治理、工业数据看板四大服务&#xff0c;构建工业感知神经系统新型数…

yolov5 V7.0版本 使用Pascal voc 2012 数据集训练

1、环境搭建 # 1、anaconda pycharm环境搭建 https://blog.csdn.net/weixin_45715405/article/details/132100595?spm1001.2014.3001.5502 根据上面创建一个conda的虚拟环境python版本为3.8版本# 2、yolov5 代码下载 https://github.com/ultralytics/yolov5# 3、安装需要的依…

数据+关键字驱动——实现RF登录模块的接口自动化实例

前言 在之前的篇章中用一张图片介绍了使用RF搭建的自动化框架&#xff0c;接下来讲解登录模块的接口自动化实例。 通过数据驱动&#xff08;用例管理&#xff09;关键字驱动&#xff08;业务逻辑&#xff09;双引擎驱动模式将测试数据与业务逻辑分离&#xff0c;测试用例只需要…

Lnton羚通云算力平台【PyTorch】教程:关于Tensors的基础知识

Tensors Tensors 是一个特殊的数据结构&#xff0c;非常类似于数组和矩阵&#xff0c;在 PyTorch 中&#xff0c;我们使用 tensors 编码模型的输入和输出&#xff0c;以及模型的参数。 Tensors 非常类似于 NumPy 的 ndarrays&#xff0c; tensors 可以运行在 GPU 以及其他硬件…

mysql------做主从复制,读写分离

1.为什么要做主从复制&#xff08;主从复制的作用&#xff09; 做数据的热备&#xff0c;作为后备数据库&#xff0c;主数据库服务器故障后&#xff0c;可切换到从数据库继续工作&#xff0c;避免数据丢失。 架构的扩展。业务量越来越大,I/O访问频率过高&#xff0c;单机无法满…

UE4/5Niagara粒子特效之Niagara_Particles官方案例:2.4->3.2

之前的案例 UE4/5Niagara粒子特效之Niagara_Particles官方案例&#xff1a;1.1-&#xff1e;1.4_多方通行8的博客-CSDN博客 UE4/5Niagara粒子特效之Niagara_Particles官方案例&#xff1a;1.5-&#xff1e;2.3_多方通行8的博客-CSDN博客 2.4 Location Events 这次的项目和之…

亮点!视频云存储/安防监控视频智能分析平台高空抛物AI智能检测

一、行业现状 近年来&#xff0c;高空抛物不文明事件频频发生&#xff0c;成为小区住宅的管理通病&#xff0c;也给居民的人身及财产安全带来了巨大伤害和损失。高空抛物可能导致人身事故等重大经济损失的严重危害&#xff0c;被称作“悬在城市上空的痛”。 TSINGSEE青犀AI智…
最新文章