P12444 [COTS 2025] 发好奖 / Hijerarhija

题目描述

$N$ 个人的上下级关系构成一棵树。第 $1$ 个人为总监，第 $i$ （ $i\ge 2$ ）个人的直接上级为 $s_i$ 。

现在要给员工分配奖金。每个人的奖金可以是正整数，或者 $0$ （没有奖金）。如果第 $i$ 个人获得了至少 $c_i$ 的奖金，下一年他的积极性会提高 $p_i$ ，否则积极性不会提高。

并非所有人都必须获得奖金，但是每个获得奖金的人的直接上级必须获得至少 $1$ 的奖金。

在发出的奖金总额不超过 $K$ 的前提下，求出积极性提高的总和最大值。

输入格式

$N$ $K$
$s_2$ $s_3$ $\ldots$ $s_N$
$p_1$ $p_2$ $\ldots$ $p_N$
$c_1$ $c_2$ $\ldots$ $c_N$

输出格式

一行一个非负整数，表示答案。

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

输入输出样例 #3

输入 #3

输出 #3

说明/提示

样例解释

样例 $2$ 解释：

一个合法的奖金分配方案：员工依次获得的奖金为 $1,1,0,2,3$ 。

分配方案 $1,1,1,2,3$ 不合法，因为奖金超支了。

分配方案 $0,1,1,2,3$ 同样不合法，因为第 $2$ 个人获得了奖金，但其直接上级未获得。

数据范围

$2\le N\le 5\, 000$ ；
$1\le K\le 5\, 000$ ；
$1\le p_i\le 10^5$ ；
$1\le c_i\le 5\, 000$ ；
$1\le s_i\lt i$ ；
输入的所有值均为整数。

子任务

子任务 $0$ 为样例。

其中，「 $-$ 」表示「不保证」。

子任务编号	$N\le$	$K\le$	特殊性质	得分
$1$	$20$	$-$	$-$	$7$
$2$	$-$	$-$	$\text{A}$	$9$
$3$	$-$	$-$	$\text{B}$	$14$
$4$	$500$	$500$	$-$	$19$
$5$	$100$	$-$	$-$	$21$
$6$	$-$	$-$	$-$	$30$

特殊性质 $\text{A}$ ： $c_i=1$ ，且 $j$ 是 $i$ 的上级 $\implies$ $p_j\ge p_i$ 。
特殊性质 $\text{B}$ ： $\forall 2\le i\le N$ ， $s_i=i-1$ 。C++代码，仔细思考，这不是简单题

题目描述

N

个人的上下级关系构成一棵树。第

1

个人为总监，第

i

（

i\ge 2

）个人的直接上级为

s_i

。

现在要给员工分配奖金。每个人的奖金可以是正整数，或者

0

（没有奖金）。如果第

i

个人获得了至少

c_i

的奖金，下一年他的积极性会提高

p_i

，否则积极性不会提高。

并非所有人都必须获得奖金，但是每个获得奖金的人的直接上级必须获得至少

1

的奖金。

在发出的奖金总额不超过

K

的前提下，求出积极性提高的总和最大值。

说明/提示

样例解释

样例

2

解释：

一个合法的奖金分配方案：员工依次获得的奖金为

1,1,0,2,3

。

分配方案

1,1,1,2,3

不合法，因为奖金超支了。

分配方案

0,1,1,2,3

同样不合法，因为第

2

个人获得了奖金，但其直接上级未获得。

数据范围

2\le N\le 5\, 000

；

1\le K\le 5\, 000

；

1\le p_i\le 10^5

；

1\le c_i\le 5\, 000

；

1\le s_i\lt i

；

输入的所有值均为整数。

子任务

0

为样例。

其中，「

-

」表示「不保证」。

子任务编号

N\le

K\le

特殊性质

得分

1

20

-

-

7

2

-

-

\text{A}

9

3

-

-

\text{B}

14

4

500

500

-

19

5

100

-

-

21

6

-

-

-

30

特殊性质

\text{A}

：

c_i=1

，且

j

是

i

的上级

\implies

p_j\ge p_i

。

特殊性质

\text{B}

：

\forall 2\le i\le N

，

s_i=i-1

。C++代码，仔细思考，这不是简单题

# P12444 [COTS 2025] 发好奖 / Hijerarhija ## 题目描述 $...

Domanda

P12444 [COTS 2025] 发好奖 / Hijerarhija

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

输入输出样例 #3

输入 #3

输出 #3

说明/提示

样例解释

数据范围

子任务

Domanda

P12444 [COTS 2025] 发好奖 / Hijerarhija

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

输入输出样例 #3

输入 #3

输出 #3

说明/提示

样例解释

数据范围

子任务

Condividi questa Q&A