#805. [USACO24Jan Silver] Potion Farming

[USACO24Jan Silver] Potion Farming

题目来源:2024 年 USACO 银组一月月赛 T2。题目翻译来自洛谷。

题目描述

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

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

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

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

输入格式

输入的第一行包含一个整数 NN,为地图内的房间数量。

以下一行包含 NN 个空格分隔的整数 p1p2pNp_1p_2\ldots p_N,其中 pip_i 为第 ii 次遍历之前药水出现的房间。

最后 N1N−1 行每行包含两个空格分隔的整数 a ba\ b1a,bN1\le a,b\le N),表示房间 aabb 之间的一条边。输入保证所有边形成一棵树。

输出格式

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

样例 #1

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

提示

样例解释 1

在这个测试用例中,通关地图所需的最小遍历次数为 33

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

  • 遍历 111351\to 3\to 5(于房间 55 拾取药水)
  • 遍历 221341\to 3\to 4(于房间 44 拾取药水)
  • 遍历 33121\to 2(被迫通关地图,无视房间 33 的药水)

或者,我们也可以计划我们的遍历如下:

  • 遍历 11121\to 2(没有药水)
  • 遍历 221341\to 3\to 4(于房间 44 拾取药水)
  • 遍历 331351\to 3\to 5(于房间 33 拾取药水)

测试点性质

  • 测试点 272-7N1000N\le 1000
  • 测试点 8158-15:没有额外限制。