P9352 [JOI 2023 Final] 训猫 / Cat Exercise

有 $N$ 个猫塔，编号从 $1$ 到 $N$。塔 $i$ 的高度为 $P_i$（$1 \le i \le N$）。这些塔的高度是 $1$ 到 $N$ 之间的不同整数。共有 $N - 1$ 对相邻的塔。对于每个 $j$（$1 \le j \le N - 1$），塔 $A_j$ 和塔 $B_j$ 是相邻的。最开始，可以通过从一个塔移动到相邻的塔，来从一个塔到达任何其他塔。 最开始，一只猫待在高度为 $N$ 的塔上。 然后我们进行**猫运动**。在猫运动中，我们反复选择一个塔并在其上放置一个障碍。然而，我们不能在已经放置障碍的塔上再放置障碍。在这个过程中，将发生以下情况： - 如果猫不在所选的塔上，什么也不会发生。 - 如果猫在所选的塔上，并且所选塔的每个相邻塔上都有障碍，猫运动将结束。 - 否则，在猫可以通过从塔移动到相邻塔而不受障碍影响到达的塔中，猫将移动到除当前塔外最高的塔。过程中，猫会选择从塔移动到相邻塔的步数最少的路线。 给定塔的高度信息和相邻塔的对，编写程序计算在适当放置障碍的情况下，猫从塔移动到相邻塔的最大可能移动次数之和。

从标准输入读取以下数据。 > $N$ > $P_1$ $P_2$ $\cdots$ $P_N$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_{N-1}$ $B_{N-1}$

向标准输出写入一行。输出应包含猫从塔移动到相邻塔的最大可能移动次数之和。

## 样例 ### 样例 1 如果我们按以下方式进行猫运动，猫总共移动 3 次。 - 我们在塔 1 上放置一个障碍。猫不移动。 - 我们在塔 2 上放置一个障碍。猫从塔 2 移动到塔 3。然后，猫从塔 3 移动到塔 4。 - 我们在塔 4 上放置一个障碍。猫从塔 4 移动到塔 3。 - 我们在塔 3 上放置一个障碍。然后猫运动结束。 由于没有办法进行猫运动，使得猫从塔移动到相邻塔的次数大于或等于 4，因此输出 3。 此样例输入满足子任务 1、2、3、4、5、7 的约束。 ### 样例 2 此样例输入满足子任务 4、6、7 的约束。 ## 约束 - $2 \le N \le 2\times 10^5$。 - $1 \le P_i \le N$ ($1 \le i \le N$)。 - $P_i \neq P_j$ ($1 \le i < j \le N$)。 - $1 \le A_j < B_j \le N$ ($1 \le j \le N - 1$)。 - 最开始，可以通过从一个塔移动到相邻塔，来从一个塔到达任何其他塔。 - 给定的值都是整数。 ## 子任务 1. (7 分) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$)，$N \le 16$。 2. (7 分) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$)，$N \le 300$。 3. (7 分) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$)，$N \le 5 000$。 4. (10 分) $N \le 5 000$。 5. (20 分) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$)。 6. (23 分) $A_i =\left\lfloor\frac{i+1}2\right\rfloor, B_i = i + 1$ ($1 \le i \le N - 1$)。这里 $\lfloor x \rfloor$ 是小于或等于 $x$ 的最大整数。 7. (26 分) 无额外约束。 题面翻译由 ChatGPT-4o 提供。