06728. USACO·药水采收 未做

你正在玩你最喜欢的手机游戏。为了有机会击败传说中的奶牛 Boss，你正在试着刷药水。游戏地图是由 $N$（$2\le N\le 10^5$）个编号为 $1\dots N$ 的房间组成，由 $N-1$ 条边连接，形成一棵树。

你可以通过一系列的「遍历」来探索地图。一次遍历是从房间 $1$ 到树中任何其他房间的一条简单路径。当你完成一次遍历后，你可以从房间 $1$ 再次开始遍历。一旦地图的每个房间都被至少一次遍历访问过，这个地图就通关了。你的主要目标是以最小的遍历次数通关这一地图。

你的次要目标是刷到尽可能多的药水。在一次遍历开始前，地图上的某个房间内会生成一瓶药水。你可以通过在当次遍历中访问生成药水的房间来拾取药水。如果你没有拾取药水，那么当次遍历结束它就会消失，你无法在未来的遍历中拾取它。

由于你是一位聪明的程序员，在查看游戏文件后，你成功知道了在接下来的 $N$ 次遍历之前药水的出现位置。如果你以最小的遍历次数通关地图，你可以从地图内刷到的最大药水数量是多少？

输入的第一行包含一个整数 $N$，为地图内的房间数量。

以下一行包含 $N$ 个空格分隔的整数 $p_1{p}_2\dots p_N$，其中 $p_i$ 为第 $i$ 次遍历之前药水出现的房间。

最后 $N-1$ 行每行包含两个空格分隔的整数 $ab$（$1\le a,b\le N$），表示房间 $a$ 和 $b$ 之间的一条边。输入保证所有边形成一棵树。

输出一行，包含一个整数，为以最小的遍历次数可以从地图内刷到的最大药水数量。

【样例解释】

在这个测试用例中，通关地图所需的最小遍历次数为 $3$。

一个在三次遍历中拾取两瓶药水的最佳方案如下：

• 遍历 1：$1\to 3\to 5$（于房间 5 拾取药水）

• 遍历 2：$1\to 3\to 4$（于房间 4 拾取药水）

• 遍历 3：$1\to 2$（被迫通关地图，无视房间 3 的药水）

或者，我们也可以计划我们的遍历如下：

• 遍历 1：$1\to 2$（没有药水）

• 遍历 2：$1\to 3\to 4$（于房间 4 拾取药水）

• 遍历 3：$1\to 3\to 5$（于房间 3 拾取药水）

• 测试点 8-15：没有额外限制。

【数据规模与约定】

• 测试点 2-7：$N\le 1000$。

• 测试点 8-15：没有额外限制。

供题：Suhas Nagar