首页 > 试题广场 >

没有上司的舞会

[编程题]没有上司的舞会
  • 热度指数：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。

备注:

算法知识视频讲解
添加回答
Sen🍓🍀头像 Sen🍓🍀
打家劫舍 → 父子节点不能连续选 (树形DP)
发表于 2025-10-14 17:03:12 回复(0)
提交观点

问题信息

难度：
1条回答 67浏览

热门推荐

相关试题

没有上司的舞会

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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