首页 > 试题广场 >

没有上司的舞会

[编程题]没有上司的舞会
  • 热度指数：148 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
\hspace{15pt}公司准备举办一场晚会，为了让到场的员工尽情放松，公司规定：若邀请了某名员工，则绝不邀请ta的直接上司；而上司的上司、上司的上司的上司……则不受限制。已知每名员工至多只有一位直接上司（总 \texttt{boss} 是公司的老板，没有直接上司），因此整张"上下级关系图"是一棵以总 \texttt{boss} 为根的树。

\hspace{15pt}第 i 名员工被邀请时能够为晚会增添 w_i 点气氛值（w_i 可能为负）。请你为公司规划一份邀请名单，使得气氛值总和最大。

输入描述:
\hspace{15pt}第一行输入一个整数 n\left(1\leqq n\leqq2\times10^5\right)――员工数量。

\hspace{15pt}第二行输入 n 个整数 w_1,w_2,\dots,w_n\left(-128\leqq w_i\leqq127\right)――每名员工对应的气氛值。

\hspace{15pt}此后 n-1 行，每行输入两个整数 k,\,\ell\left(1\leqq k,\ell\leqq n\right)，表示k是ℓ的直接上司。


输出描述:
\hspace{15pt}输出一个整数，代表在满足规则的前提下可获得的最大气氛值总和。
示例1

输入

4
1 7 3 4
1 2
2 3
2 4

输出

8

说明

\hspace{15pt}如上图，整棵树以员工 1 为根。若邀请员工 2 与 3，可得 w_2+w_3=7+3=10，

\hspace{15pt}若邀请员工 1 与 3 与 4，会违反"上下级不得同时出席"的规则。

\hspace{15pt}在最优方案中可邀请员工 2 与 4，得到最大气氛值 7+4=11。

备注:

算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-01 13:57:41
HIGH93 没有上司的舞会 题目描述 公司准备举办一场晚会，共有 名员工。每名员工都有一个“气氛值”，邀请他们可以为晚会增加对应的气氛值。 规则是：如果邀请了一名员工，那么他的直接上司就不能被邀请。 已知公司的层级关系是一棵树，根节点是老板。请求出一个邀请方案，使得晚会的总气氛值最大。 解题思 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Silencer76
发表于 2025-08-22 00:55:45
题目链接 没有上司的舞会 题目描述 公司要举办一场晚会，员工的上下级关系构成一棵树。规定如果邀请了某名员工，则不能邀请他的直接上司。每名员工参加晚会都能为晚会增添一份气氛值（可能为负数）。请求出晚会可能获得的最大气氛值总和。 输入: 第一行输入一个整数 ，表示员工数量。 第二行输入 个整数，表示 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
1条回答 70浏览

热门推荐

相关试题

没有上司的舞会

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号