← 返回题目列表

Codeforces · 1790/F

F. 蒂莫菲和黑白树

中文机器翻译题面 查看原题

Timofey 来到一所著名的暑期学校,在 $$$n$$$ 个顶点上发现了一棵树。树是无环的连通无向图。

这棵树的每个顶点($$$c_0$$$ 除外)都是白色的。顶点 $$$c_0$$$ 颜色为黑色。

Timofey 想要将这棵树的所有顶点着色为黑色。为此,他执行 $$$n - 1$$$ 操作。在第 $$$i$$$ 操作期间,他选择当前为白色的顶点 $$$c_i$$$,并将其涂成黑色。

我们将树的正性称为树中所有不同黑色顶点对之间的最小距离。顶点 $$$v$$$ 和 $$$u$$$ 之间的距离是从 $$$v$$$ 到 $$$u$$$ 的路径上的边数。

每次操作后,Timofey 都想知道当前树的积极性。

输入

第一行包含整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含整数 $$$n, c_0$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le c_0 \le n$$$) - 树中的顶点数和初始黑色顶点的索引。

每个测试用例的第二行包含 $$$n - 1$$$ 唯一整数 $$$c_1, c_2, \dots, c_{n-1}$$$ ($$$1 \le c_i \le n$$$, $$$c_i \ne c_0$$$),其中 $$$c_i$$$ 是在第 $$$i$$$ 次操作。

每个测试用例的接下来的 $$$n - 1$$$ 行都包含整数 $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — 树中的边。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行上打印 $$$n - 1$$$ 整数。

索引为 $$$i$$$ 的整数必须等于通过第一个 $$$i$$$ 操作获得的树的正值。

示例

输入 #1

6
6 6
4 1 3 5 2
2 4
6 5
5 3
3 4
1 3
4 2
4 1 3
3 1
2 3
1 4
10 3
10 7 6 5 2 9 8 1 4
1 2
1 3
4 5
4 3
6 4
8 7
9 8
10 8
1 8
7 3
7 5 1 2 4 6
1 2
3 2
4 5
3 4
6 5
7 6
9 7
9 3 1 4 2 6 8 5
4 1
8 9
4 8
2 6
7 3
2 4
3 5
5 4
10 2
1 8 5 10 6 9 4 3 7
10 7
7 8
3 6
9 7
7 6
4 2
1 6
7 5
9 2

输出 #1

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

注意

在第一个测试用例中,在第二次操作之后,树如下所示:

顶点 $$$1$$$ 和 $$$6$$$ 之间的距离为 $$$3$$$,顶点 $$$4$$$ 和 $$$6$$$ 之间的距离为 $$$3$$$,顶点 $$$1$$$ 和 $$$4$$$ 之间的距离为 $$$2$$$。这棵树的正值等于这些距离的最小值。它等于$$$2$$$。

在第三个测试用例中,第四次操作之后,树如下所示:

这棵树的积极性是$$$2$$$。