You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

5
5 4 3 2 1
1 2
1 3
3 4
3 5

2

提示

样例解释 1

在这个测试用例中，通关地图所需的最小遍历次数为 $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$ 拾取药水）

测试点性质

• 测试点 $2-7$：$N\le 1000$。
• 测试点 $8-15$：没有额外限制。