P3571 [POI 2014] SUP-Supercomputer

题目链接：P3571 [POI 2014] SUP-Supercomputer - 洛谷。

本题是经典斜率优化题型。

题目描述

Byteasar has designed a supercomputer of novel architecture.

It may comprise of many (identical) processing units.

Each processing unit can execute a single instruction per time unit.

The programs for this computer are not sequential but rather have a tree structure.

Each instruction may have zero, one, or multiple subsequent instructions, for which it is the parent instruction.

The instructions of the program can be executed in parallel on all available processing units. Moreover, they can be executed in many orders: the only restriction is that an instruction cannot be executed unless its parent instruction has been executed before. For example, as many subsequent instructions of an instruction that has been executed already can be executed in parallel as there are processing units.

Byteasar has a certain program to run. Since he likes utilizing his resources optimally, he is wondering how the number of processing units would affect the running time.

He asks you to determine, for a given program and number of processing units, the minimum execution time of the program on a supercomputer with this many processing units.

Byteasar 设计了一台架构新颖的超级计算机。

它可能由多个（相同的）处理单元组成。

每个处理单元每个时间单位可以执行一条指令。

这台计算机的程序不是顺序的，而是树形结构。

每条指令可能有零条、一条或多条后续指令，这些后续指令是它的父指令。

该程序的指令可以在所有可用的处理单元上并行执行。此外，它们可以按多种顺序执行：唯一的限制是，除非父指令之前已经执行过，否则指令无法执行。例如，一条已经执行过的指令的后续指令可以并行执行的数量与处理单元的数量相同。

Byteasar 有一个要运行的程序。由于他喜欢以最佳方式利用资源，因此他想知道处理单元的数量会如何影响运行时间。

他要求你确定，对于给定的程序和处理单元的数量，该程序在具有这么多处理单元的超级计算机上的最短执行时间。

输入格式

In the first line of standard input, there are two integers, $n$ and $q$ ($1\le n,q\le 1000000$), separated by a single space, that specify the number of instructions in Byteasar's program and the number of running time queries (for different numbers of processing units).

In the second line of input, there is a sequence of $q$ integers, $k_1,k_2,\cdots ,k_q$ ($1\le k_i\le 1000000$), separated by single spaces: $k_i$ is the number of processing units in Byteasar's $i$-th query.

In the third and last input line, there is a sequence of $n-1$ integers, $a_2,a_3,\cdots ,a_n$($1\le a_i<i$) separated by single spaces: $a_i$ specifies the number of the parent instruction of the instruction number $i$. The instructions are numbered with successive integers from 1 to $n$, where the instruction no. 1 is the first instruction of the program.

标准输入的第一行包含两个整数 $n$ 和 $q$（$1\le n,q\le 1000000$），两个整数之间用一个空格隔开，分别表示 Byteasar 程序中的指令数和运行时间查询的数量（针对不同数量的处理单元）。

输入的第二行包含一个 $q$ 个整数序列，$k_1,k_2,\cdots ,k_q$（$1\le k_i\le 1000000$），两个整数之间用一个空格隔开：$k_i$ 表示 Byteasar 第 $i$ 个查询中的处理单元数量。

在第三行（也是最后一行）输入中，有一个由 $n-1$ 个整数组成的序列，$a_2,a_3,\cdots ,a_n$（$1\le a_i<i$），每个整数之间用单个空格分隔：$a_i$ 表示指令号 $i$ 的父指令编号。这些指令使用从 1 到 $n$ 的连续整数编号，其中指令号 1 是程序的第一条指令。

输出格式

Your program should print one line consisting of $q$ integers, separated by single spaces, to the standard output:

the $i$-th of these numbers should specify the minimum execution time of the program on a supercomputer with $k_i$ processing units.

你的程序应该在标准输出中打印一行由 $q$ 个整数组成，每个整数之间用空格分隔：

这些数字中的第 $i$ 个应该指定该程序在具有 $k_i$ 个处理单元的超级计算机上的最小执行时间。

输入输出样例 #1

输入 #1

20 1
3
1 1 1 3 4 3 2 8 6 9 10 12 12 13 14 11 11 11 11

输出 #1

8

题解

题意转化

将“父节点已被访问的节点才能被访问”这一访问节点的操作转化为从树上删除叶子结点的操作。现在题意转化为：每次可以删除至多 $k$ 个叶子结点，最少多少次操作可以删除整棵树？

方案构造

很容易想到这一贪心方案：

	情况	操作
1	当前叶子结点至少有 $k$ 个	删除 $k$ 个最深的结点
2	当前叶子结点少于 $k$ 个	删除当前所有叶子结点（只能删除一层叶子）

在询问 $k$ 下，令 $h_k$ 表示情况 2 第一次出现时树的深度；$s_{h_k+1}$ 表示深度不小于 $h_k+1$ 的节点个数。

显然会有 $\lceil \frac{s_{h_k+1}}{k}\rceil$ 次操作 1，此后 $h_k$ 次操作 2。我们只要计算出合适的 $h_k$ 就能找到对应的 $f(k)=h_k+\lceil \frac{s_{h_k+1}}{k}\rceil$。

直接给出结论：

$$\begin{gathered} h_k=\arg \underset{0\le h\le H}{max}\{h+\lceil \frac{s_{h+1}}{k}\rceil \}\text{ \\ f(k)=hk+⌈shk+1k⌉=maxh{h+⌈sh+1k⌉}} \end{gathered}$$

也就是说，使得 $h+\lceil \frac{s_{h+1}}{k}\rceil$ 最大的 $h$ 就是我们要找的 $h_k$。正确性证明如下：

• 如果枚举的 $h$ 过大，即 $h>h_k$，会比 $h_k$ 更早按照进行操作 2，此时叶子结点必然多于 $k$ 个。此时直接操作 2“删除当前所有叶子结点”是不合法操作，且会导致总操作数 $h+\lceil \frac{s_{h+1}}{k}\rceil$ 更小；
• 如果枚举的 $h$ 过小，即 $h<h_k$，会比 $h_k$ 更晚按照情况 2 操作，必然意味着先前叶子结点不足 $k$ 个时进行了操作 1“$k$ 个最深的节点”是不合法操作，且会导致总操作数 $h+\lceil \frac{s_{h+1}}{k}\rceil$ 更小。

因此，只有合法的 $h=h_k$ 时，总操作数表达式 $h+\lceil \frac{s_{h+1}}{k}\rceil$ 取到最大值，即 $h_k=\arg \underset{0\le h\le H}{max}\{h+\lceil \frac{s_{h+1}}{k}\rceil \}$。

斜率优化

将方程进一步变形（为了与斜率 $k$ 不重名，将询问用 $i$ 表示）：

$$f(i)=\underset{h}{max}\{h+\lceil \frac{s_{h+1}}{i}\rceil \}=\underset{h}{max}\{\lceil \frac{ih+s_{h+1}}{i}\rceil \}$$

只要设法让 $ih+s_{h+1}$ 最大即可。令：

显然 $k_i$ 随着 $i$ 的增加而单调减少。维护一个上凸壳即可完成均摊 $O(1)$ 的状态转移。