CF2277C Edge Addeleting

你有一棵含有 $n$ 个顶点的树，顶点编号从 $1$ 到 $n$。 你需要在这棵树上进行 $m$ 次操作。第 $i$ 次操作包括两步： 1. 在顶点 $1$ 和顶点 $v_i$ 之间添加一条边，这会形成一个环； 2. 你从这个环上选择一条边（可以是新加的边），将其删除，使得图再次成为一棵树。 如果顶点 $1$ 和顶点 $v_i$ 之间已经有一条边，你仍然添加新的边，此时环由这两条平行边组成。 请你求出所有 $m$ 次操作完成后，顶点 $1$ 和顶点 $n$ 之间可能的最大距离$^\ast$。 $^\ast$ 树中两个顶点之间的距离是它们之间唯一一条简单路径上的边数。

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 5 \cdot 10^5$，$1 \le m \le 5 \cdot 10^5$），即顶点数和操作数。 接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$，$x \ne y$），表示初始树中的一条边。保证这些边构成一棵树。 下一行包含 $m$ 个整数 $v_1, v_2, \ldots, v_m$（$2 \le v_i \le n$），描述每次操作添加边的目标点。 保证所有测试用例中 $n$ 的总和不超过 $5\cdot 10^5$。 保证所有测试用例中 $m$ 的总和不超过 $5\cdot 10^5$。

对于每个测试用例，输出一个整数，即经过所有 $m$ 次操作后顶点 $1$ 和顶点 $n$ 之间可能的最大距离。

在第一个测试用例中，树只有一条边 $(1, 2)$，每次操作后都保持不变，因此答案是 $1$。 在第二个测试用例中，顶点 $1$ 到 $3$ 的距离初始为 $2$，任意操作都无法增加该距离。因此答案是 $2$。 在第三个测试用例中，第一次操作可以选择删除新加的边。第二次操作添加了边 $(1, 5)$，然后删除了边 $(1, 2)$。此后，$1$ 到 $7$ 的路径为 $1 \to 5 \to 4 \to 2 \to 3 \to 7$，路径长度为 $5$。可以证明无法得到更长距离，因此答案是 $5$。 由 ChatGPT 5 翻译