T454243 「2024 百度之星选拔赛」猫猫巫女灵梦


灵梦今天一觉睡到中午才醒来，结果发现自己变成了猫猫？！ 这大概是由于整天不务正业，只知道喝茶睡觉收香火钱的缘故吧。 魔理沙看到灵梦变成猫猫后感到很高兴（？？？），她给猫猫巫女灵梦买了 $n$ 个木桩。 木桩的编号从 $1 \sim n$，每个木桩有一个高度 $h_i$。 这些木桩的高度是 $1 \sim n$ 之间并且 **互不相同** 的整数。 在 $n$ 个木桩中有 $n - 1$ 对木桩之间彼此相邻，并且从任意一个木桩出发都可以到达其他任意的木桩。 猫猫巫女灵梦起初在高度最高的木桩上。 一次移动指的是从一个木桩移动到相邻的一个木桩。 魔理沙决定~~趁此良机~~训练一下猫猫巫女灵梦以便灵梦可以熟悉现在自己的躯体。 在训练过程中，魔理沙每次会选择一个木桩并在这个木桩上放置一个毒蘑菇，以阻碍猫猫灵梦的移动（前提是先前这个木桩上没有放置毒蘑菇）。 在每次选择一个木桩放置毒蘑菇之前： - 若猫猫巫女灵梦当前不处于这次选择的放置毒蘑菇的木桩，那么猫猫巫女灵梦会在这个木桩上睡大觉； - 若猫猫巫女灵梦当前处于这次选择的放置毒蘑菇的木桩，她将会移动到 **所有可到达木桩** 中 **最高** 的木桩上（移动过程中不能经过有毒蘑菇的木桩）； - 但是，若猫猫巫女灵梦当前处于这次选择的放置毒蘑菇的木桩，同时相邻的木桩也都被放了毒蘑菇，那么猫猫巫女灵梦就再也无法移动了。 请你计算出猫猫巫女灵梦 **最多可能移动多少次**。

第一行输入一个整数 $n$ $\;$ ($2 \le n \le 2\times 10^5$)，表示木桩的数量。 第二行输入 $n$ 个整数 $h_1, h_2, \ldots, h_n$ $\;$ ($1 \le h_i \le n, 1 \le i \le n$，且 $h_i$ 构成的集合等于 $\{1, 2, \ldots, n\}$)，表示每个木桩的高度。 接下来 $n - 1$ 行，每行输入两个整数 $u, v$ $\;$ ($1 \le u, v \le n, u\not = v$)，表示 $u$ 和 $v$ 编号的木桩之间彼此相邻。

输出一行一个整数，表示答案。

对于样例1： 猫猫巫女灵梦最多可以移动 $3$ 次。 - 放置一个毒蘑菇在编号 $1$ 的木桩上，猫猫灵梦原地不动； - 放置一个毒蘑菇在编号 $2$ 的木桩上，猫猫灵梦会移动到木桩 $4$ 上，移动了 $2$ 次； - 放置一个毒蘑菇在编号 $4$ 的木桩上，猫猫灵梦会移动到木桩 $3$ 上，移动了 $1$ 次； - 最后放置一个毒蘑菇在编号 $3$ 的木桩上，猫猫巫女灵梦不再移动了。 故最终猫猫巫女灵梦移动了 $3$ 次。 没有任何其他方式可以使得猫猫巫女灵梦可以移动更多的次数。