← 返回题目列表

AtCoder · joi2023ho_d

D. 猫练习

中文机器翻译题面 查看原题

配点: 100 点

問題文

N 猫塔,每个塔都有 它们的编号最大为 1 到 N 。 塔 i (1 \leqq i \leqq N) 的高度是 P_i 。 塔的高度是 1 以上 N 是以下不同的整数。 N-1 一组塔楼彼此相邻,并且每个塔楼 j (1 \leqq j \leqq N-1), 塔 A_j 和塔 B_j 相邻。 最初,您可以通过重复移动到相邻塔的操作从任何塔移动到任何塔。

一开始猫很高 你位于 N 塔顶。

接下来,猫练习 执行。 什么是猫运动?1 这是选择一个塔并在那里放置障碍物的重复操作。 但是,无法在已放置障碍物的塔上再次放置障碍物。 操作结果如下。

  • 如果所选塔中没有猫,则不会发生任何事情。
  • 如果所选塔中有一只猫,并且所有相邻塔中都放置了障碍物,则猫练习结束。
  • 如果这两种情况都不是,猫会通过重复移动到没有障碍物的相邻塔,然后从所选塔移动到可以移动的最高塔(不包括所选塔),然后重复移动到相邻塔来移动。这时猫会移动,使得移动到相邻塔的次数最小化。

给定一座塔的高度和一组相邻塔的高度, 编写一个程序,找出当设置障碍物时,猫移动到相邻塔的最大总次数。


入力

输入是按以下格式从标准输入给出的。

N
P_1 P_2 \cdots P_N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

猫移动到相邻塔的最大总次数被写入标准输出。 输出为 1 行。


制約

  • 2 \leqq N \leqq 200\,000.
  • 1 \leqq P_i \leqq N (1 \leqq i \leqq N).
  • P_i \neq P_j (1 \leqq i < j \leqq N).
  • 1 \leqq A_j < B_j \leqq N (1 \leqq j \leqq N-1).
  • 最初,您可以通过重复移动到相邻塔的操作从任何塔移动到任何塔。
  • 所有输入值都是整数。

小課題

  1. (7 点) A_i=i,B_i=i+1 (1 \leqq i \leqq N-1),N \leqq 16.
  2. (7 点) A_i=i,B_i=i+1 (1 \leqq i \leqq N-1),N \leqq 300.
  3. (7 点) A_i=i,B_i=i+1 (1 \leqq i \leqq N-1),N \leqq 5\,000.
  4. (10 点) N \leqq 5\,000.
  5. (20 点) A_i=i,B_i=i+1 (1 \leqq i \leqq N-1).
  6. (23 点) A_i=\left\lfloor \frac{i+1}{2} \right\rfloor,B_i=i+1 (1 \leqq i \leqq N-1).然而, 表示\lfloor x \rfloor 满足 x 的值向下舍入到小数点。
  7. (26 点)没有额外的限制。

入力例 1

4
3 4 1 2
1 2
2 3
3 4

出力例 1

3

当进行如下所示的猫练习时,猫会 移动 3 次。

  • 塔 在 1 处放置障碍物。这时,猫一动不动。 在
  • 塔 在 2 处放置障碍物。这时,猫在塔里 2 来自塔楼 前往 3 ,然后前往塔楼 移至 3 来自塔楼 前往 4 。 在
  • 塔 在 4 处放置障碍物。这时,猫在塔里 4 来自塔楼 前往 3 。 在
  • 塔 在 3 处放置一个障碍物。猫的练习到这里就结束了。

猫 4 猫的锻炼方法中没有涉及多次移动到相邻塔的方法。3 。

此输入示例是一个小作业。 1,2,3,4,5,7 满足约束。


入力例 2

7
3 2 7 1 5 4 6
1 2
1 3
2 4
2 5
3 6
3 7

出力例 2

7

此输入示例是一个小作业。 4,6,7 满足约束。