AT_joi2023ho_d キャットエクササイズ (Cat Exercise)

有 $N$ 个猫塔，每个猫塔编号为 $1$ 到 $N$。第 $i$ 号猫塔的高度为 $P_i$。所有猫塔的高度 $P_i$ 是 $1$ 到 $N$ 的互不相同的整数。共有 $N-1$ 对猫塔相邻，对于每个 $j$（$1 \leq j \leq N-1$），猫塔 $A_j$ 与猫塔 $B_j$ 相邻。初始时，任意一对猫塔之间都可以通过一系列相邻猫塔的移动连通。 一只猫最初位于高度为 $N$ 的猫塔上。 接下来进行**猫咪体操**。猫咪体操是指重复以下操作：每次选择一个猫塔并在其上放置一个障碍物。已经放置障碍物的猫塔不能再次放置。每次操作会根据下列情况发生变化： - 如果选中的猫塔上没有猫，则什么也不会发生。 - 如果选中的猫塔上有猫，且所有与之相邻的猫塔都已放置了障碍物，则猫咪体操结束。 - 否则，猫会从选中的猫塔出发，反复通过未放置障碍物的相邻猫塔进行移动，最终移动到从当前塔可达的其它猫塔中除选中的猫塔以外的最高的那一座上。此时猫选择使相邻塔间移动次数最少的路径到达目标塔。 给定猫塔高度和相邻关系的信息，要求编写程序，计算合理选择放置障碍物的位置，使猫在相邻塔之间移动的总步数最大，输出这个最大值。

输入按以下格式从标准输入给出。 > $N$ > $P_1$ $P_2$ $\cdots$ $P_N$ > $A_1$ $B_1$ > $A_2$ $B_2$ > ⋮ > $A_{N-1}$ $B_{N-1}$

请输出一行，表示猫在相邻塔之间移动的总步数的最大值。

## 小子任务 1. （$7$ 分）$A_i=i$，$B_i=i+1$（$1 \leq i \leq N-1$），$N \leq 16$。 2. （$7$ 分）$A_i=i$，$B_i=i+1$（$1 \leq i \leq N-1$），$N \leq 300$。 3. （$7$ 分）$A_i=i$，$B_i=i+1$（$1 \leq i \leq N-1$），$N \leq 5000$。 4. （$10$ 分）$N \leq 5000$。 5. （$20$ 分）$A_i=i$，$B_i=i+1$（$1 \leq i \leq N-1$）。 6. （$23$ 分）$A_i=\left\lfloor \frac{i+1}{2} \right\rfloor$，$B_i=i+1$（$1 \leq i \leq N-1$）。其中，$\lfloor x \rfloor$ 表示对 $x$ 进行向下取整。 7. （$26$ 分）没有额外约束。 --- ## 样例解释 1 若按以下方式进行猫咪体操，猫总共移动了 $3$ 次： - 在猫塔 $1$ 放置障碍物，此时猫不移动。 - 在猫塔 $2$ 放置障碍物，此时猫从猫塔 $2$ 移动到猫塔 $3$，然后再从猫塔 $3$ 移动到猫塔 $4$。 - 在猫塔 $4$ 放置障碍物，此时猫从猫塔 $4$ 移动到猫塔 $3$。 - 在猫塔 $3$ 放置障碍物，猫咪体操结束。 不存在使猫咪体操的移动次数大于 $3$ 的方案，因此输出 $3$。 本输入样例满足小子任务 $1,2,3,4,5,7$ 的约束。 --- ## 样例解释 2 本输入样例满足小子任务 $4,6,7$ 的约束。 # 约束条件 - $2 \leq N \leq 200\,000$。 - $1 \leq P_i \leq N$（$1 \leq i \leq N$）。 - $P_i \neq P_j$（$1 \leq i < j \leq N$）。 - $1 \leq A_j < B_j \leq N$（$1 \leq j \leq N-1$）。 - 初始时，每对猫塔都能通过一系列相邻猫塔的移动连通。 - 输入的所有值均为整数。 由 ChatGPT 5 翻译