样例下载

题目描述

有 $N$ 个路口，编号为 $1$ ~ $N$。这些路口由 $N-1$ 条双向道路连接，每条道路连接两个不同的路口，任意两个路口都可以经过若干条道路互达。

在接下来的若干天，你每天的任务是巡逻。每天的巡逻从 $1$ 号路口出发，然后自己指定一个路口作为当天的目的地，沿最短路径到达目的地后，再沿原路返回。

你希望用最少的天数，使得每个路口至少被你巡逻过一次。

你的好朋友他并不知道你的巡逻安排，他只想给你一些惊喜。他不知道你要巡逻多少天，但他知道你最多巡逻 $N$ 天，所以在接下来的 $N$ 天，每天他会在某一个路口放置一个宝贝。如果你当天巡逻经过这个路口，就可以捡到这个宝贝。否则，他就会在你当天巡逻结束后把宝贝拿走。

你不经意间知道了你朋友的计划，你知道他在第 $i$ 天会在 $X_i$ 号路口放置宝贝。你当然希望能捡到更多的宝贝，但你不会为了捡到更多的宝贝而增加自己的巡逻天数。

问：在使用最少天数完成你的巡逻任务的前提下，你最多能捡到多少个宝贝？

输入格式

第一行：一个整数 $N$

第二行：$N$ 个整数 $X_i$

接下来 $N−1$ 行：每行两个整数 $U, V$，表示路口 $U$ 和 $V$ 之间有一条道路。

输出格式

一个整数，表示答案。

样例输入

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

样例输出

3

样例解释

最少需要 4 天完成巡逻任务，最多捡到 3 个宝贝。巡逻方案可能很多，以下列出两种可能的方案：

（1）第一种可能方案：

• 第 1 天：1-2-3-2-1 经过 3 号路口捡到宝贝
• 第 2 天：1-2-4-2-1 经过 4 号路口捡到宝贝
• 第 3 天：1-5-1 没有捡到宝贝
• 第 4 天：1-6-1 经过 6 号路口捡到宝贝

（2）第二种可能方案：

• 第 1 天：1-2-3-2-1 经过 3 号路口捡到宝贝
• 第 2 天：1-5-1 没有捡到宝贝
• 第 3 天：1-2-4-2-1 经过 2 号路口捡到宝贝
• 第 4 天：1-6-1 经过 6 号路口捡到宝贝

数据范围

30% 的数据：$N ≤ 10^3$。

100% 的数据：$2 ≤ N ≤ 10^5; 1 ≤ X_i, U, V ≤ N$