Potion Farming

题目描述

你正在玩你最喜欢的手机游戏，并且你正在刷取药水，以便有机会击败传说中的奶牛 Boss。游戏地图是一系列 $N$ 个房间（$2 \leq N \leq 10^5$），编号为 $1\dots N$，由 $N-1$ 条边连接，并构成一棵树。 你可以通过进行一系列“穿越（traversals）”来探索地图。一次穿越是一条从房间 $1$ 出发到树中任意其他房间的简单路径。完成一次穿越后，你可以再次从房间 $1$ 开始另一条穿越。当地图中的每一个房间都至少被某次穿越访问过一次时，地图就被视为完成。你的主要目标是在最少的穿越次数内完成地图。 你的次要目标是尽可能多地刷取药水。在一次穿越开始之前，一瓶药水会在地图中的某个房间生成。你可以在当前这次穿越中访问药水生成的房间来拾取它。如果你没有拾取该药水，那么它会在当前穿越结束时消失，因此你无法在之后的穿越中再拾取它。 由于你是一名聪明的程序员，在查看了游戏文件后，你能够提前得知接下来 $N$ 次穿越之前药水会出现在哪些房间。如果你以最少的穿越次数完成地图，那么你最多能从地图中刷到多少瓶药水？

输入格式

输入的第一行包含一个整数 $N$，表示地图中的房间数量。 接下来有 $N$ 个以空格分隔的整数 $p_1 \: p_2 \: \ldots \: p_N$，其中 $1 \leq p_i \leq N$，$p_i$ 表示第 $i$ 次穿越开始前药水将出现在的房间。 最后有 $N-1$ 行，每行包含两个以空格分隔的整数 $a \: b$（$1 \leq a, b \leq N$），表示房间 $a$ 与房间 $b$ 之间的一条边。保证这些边构成一棵树。

输出格式

输出一行，包含一个整数：在以最少穿越次数完成地图的前提下，你最多能刷到的药水数量。

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

2

提示

在这个样例中，完成地图所需的最少穿越次数是 $3$。 一种在三次穿越中拾取两瓶药水的最优方案如下： 穿越 1：$1 \rightarrow 3 \rightarrow 5$（在 5 拾取药水） 穿越 2：$1 \rightarrow 3 \rightarrow 4$（在 4 拾取药水） 穿越 3：$1 \rightarrow 2$（为完成地图被迫进行，并忽略在 3 的药水） 或者，我们也可以如下规划穿越： 穿越 1：$1 \rightarrow 2$（没有药水） 穿越 2：$1 \rightarrow 3 \rightarrow 4$（在 4 拾取药水） 穿越 3：$1 \rightarrow 3 \rightarrow 5$（在 3 拾取药水） 计分： 输入 2-7：$N\le 1000$ 输入 8-15：无额外限制。 题目来源：Suhas Nagar

标签: USACO|2024|Silver

来源

USACO|2024|Silver