分数: 550 点
问题陈述
有一棵树 N 顶点。顶点已编号 1, 2, \ldots, N,以及 i第一条边连接顶点 U_i 和 V_i.
最初,所有顶点都涂成黑色。
流程 Q 按顺序查询以下表格并找到每个查询的答案。
- 一个整数 给出了 x (1 \leq x \leq N) 。如果顶点 x 是白色的,重新漆成黑色;如果顶点 x 是黑色的,将其重新漆成白色。然后,找到两个黑色顶点之间的最大距离。这里,树上两个顶点之间的距离是它们之间的简单路径中的边数。
在给定的输入中,按顺序处理查询时始终至少有两个黑色顶点。
约束
- 3 \leq N \leq 10^5
- 1 \leq U_i, V_i \leq N
- 给定的图是一棵树。
- 1 \leq Q \leq 10^5
- 对于每个查询, 1 \leq x \leq N.
- 始终至少有两个黑色顶点。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \text{query}_i 表示 i第一个查询:
N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
每个查询均按以下格式给出:
x
输出
输出 Q 行。
的 i- 第行应包含以下问题的答案 i按顺序处理时的第一个查询。
示例输入 1
7 1 2 2 3 2 4 6 7 3 5 7 3 9 1 4 2 6 3 1 1 4 6
示例输出 1
4 3 3 2 2 3 2 3 4
- 重新绘制后 1st查询,黑色顶点是 2, 3, 4, 5, 6, 7。顶点之间的距离 4 和 6 is 4,答案是 4.
- 重新绘制后 2nd查询,黑色顶点是 2, 3, 5, 6, 7。顶点之间的距离 2 和 6 is 3,答案是 3.
- 重新绘制后 3rd查询,黑色顶点是 3, 5, 6, 7。顶点之间的距离 5 和 6 is 3,答案是 3.
- 重新绘制后 4第查询,黑色顶点是 3, 5, 7。顶点之间的距离 5 和 7 is 2,答案是 2.
- 重新绘制后 5第查询,黑色顶点是 5, 7。顶点之间的距离 5 和 7 is 2,答案是 2.
- 重新绘制后 6第查询,黑色顶点是 1, 5, 7。顶点之间的距离 1 和 5 is 3,答案是 3.
- 重新绘制后 7第查询,黑色顶点是 5, 7。顶点之间的距离 5 和 7 is 2,答案是 2.
- 重新绘制后 8第查询,黑色顶点是 4, 5, 7。顶点之间的距离 4 和 5 is 3,答案是 3.
- 重新绘制后 9第查询,黑色顶点是 4, 5, 6, 7。顶点之间的距离 4 和 6 is 4,答案是 4.
请注意,上面给出的示例只是实现最大值的一个实例。