| 题目名称 | 962. 公司聚会 |
|---|---|
| 输入输出 | cparty.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-07-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：9， 提交：29， 通过率：31.03% | ||||
 ghkkk |
100 | 0.054 s | 0.75 MiB | C++ |
 cstdio |
100 | 0.068 s | 0.63 MiB | C++ |
 Skywalker |
100 | 0.069 s | 0.73 MiB | C++ |
 Makazeu |
100 | 0.106 s | 0.77 MiB | C++ |
 馒头 |
100 | 0.111 s | 1.24 MiB | C++ |
 好啊好啊 |
100 | 0.333 s | 1.19 MiB | C++ |
 Frank |
100 | 0.353 s | 2.10 MiB | C++ |
 Kirito |
100 | 0.399 s | 8.34 MiB | C++ |
 cyezzyk |
100 | 0.407 s | 47.64 MiB | C++ |
|
cyezzyk |
50 | 0.429 s | 47.64 MiB | C++ |
| 关于 公司聚会 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
非常简单的树型DP
Frank
2016-11-18 18:02
1楼
| ||||
-
dd_engi 所在的TIANYI 公司要举办一次盛大的公司聚会。可惜的是，由于场地和花费
的原因，不可能所有人都参加。现在的任务是拟定参加聚会人员的名单。
TIANYI 公司的组织架构可以看做一棵有根多叉树。也就是说，在编号为1~N 的所有N
名员工中，除了最高管理者（编号为1）以外，每个员工都有且仅有一位直接上司；最高管
理者则是这棵多叉树的“根”。这很好理解，对吗？另外，我们保证，员工的编号会大于他
的直接上司的编号。
不同的员工对于聚会有着不同的要求，事实上，若邀请第i 位员工（编号为i），在聚会
中满足他的要求需要花费Ci 元。另一方面，不同的员工在聚会中的“兴奋指数”也不同，
第i 位员工参加聚会的兴奋指数是Ei。
选择参加聚会的人员还有一个限制：为了使参加聚会的员工能够尽量放松，若邀请了某
位员工，就不能邀请他的任何一位上司。这里“上司”的定义是这样的：最高管理者没有上
司，其余所有员工的直接上司以及直接上司的所有上司都是他的上司。换句话说，某位员工
的上司就是树中从他的节点走到根节点的路径上经过的所有节点（包括根结点，但不包括他
自身）。
在满足上述限制的前提下，dd_engi 希望参加聚会人员的兴奋指数之和最大，但同时他
被告知，满足所有参加聚会人员的要求的总花费不得超过M 元。那么，参加聚会人员的名
单究竟应该怎样确定才最优呢？你需要求出的是最大的总兴奋指数。
第一行，两个空格隔开的整数，N 与M。
第二行，N-1 个整数，分别是第2 位至第N 位员工的直接上司的编号。
第三行，N 个整数，分别是C1、C2……CN。
第四行，N 个整数，分别是E1、E2……EN。
只需输出一行一个整数，即最大的总兴奋指数。
10 100
1 2 2 1 4 3 5 6 1
12 53 127 32 164 22 199 10 19 17
-1 0 3 5 7 -2 9 6 8 13
27
30%的数据满足N<=20。
100%的数据满足1 <= N <= 1024, 0 <= M <= 109, 0 <= Ci <= 1024, -1024 <= Ei <= 1024。