配点: 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).
- 最初,您可以通过重复移动到相邻塔的操作从任何塔移动到任何塔。
- 所有输入值都是整数。
小課題
- (7 点) A_i=i,B_i=i+1 (1 \leqq i \leqq N-1),N \leqq 16.
- (7 点) A_i=i,B_i=i+1 (1 \leqq i \leqq N-1),N \leqq 300.
- (7 点) A_i=i,B_i=i+1 (1 \leqq i \leqq N-1),N \leqq 5\,000.
- (10 点) N \leqq 5\,000.
- (20 点) A_i=i,B_i=i+1 (1 \leqq i \leqq N-1).
- (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 的值向下舍入到小数点。
- (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 满足约束。