← 返回题目列表

Codeforces · 2211/E

E. 最小路径覆盖

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

不管问题名称所暗示的是什么,我们希望这个问题不是 NP 难问题。

这是一个交互问题。

给定一个有根树$$$^{\text{*}}$$$ $$$T$$$,大小为$$$m$$$,其中每个节点$$$i$$$都有一个关联值$$$a_i$$$,定义一个 垂直路径 作为节点序列 $$$[s_1,s_2,\ldots,s_p]$$$,使得 $$$s_{i+1}$$$ 是所有 $$$1 \leq i \lt p$$$ 的 $$$s_i$$$ 的子节点。垂直路径是 好 if $$$\operatorname{gcd}(a_{s_1},a_{s_2},\ldots,a_{s_p}) \neq 1$$$$$$^{\text{†}}$$$。将 $$$f(T)$$$ 定义为良好垂直路径的最小数量,使得每个节点都位于 正是 一条好路。

有一个奇怪的有 $$$n$$$ 节点的有根树,其中节点 $$$1$$$ 是根。该树满足每个节点仅具有标签大于其自身的子节点的属性。将 $$$S(u)$$$ 表示为节点 $$$u$$$ 的子树。也就是说,$$$S(u)$$$ 包含所有节点 $$$v$$$,使得从节点 $$$1$$$ 到节点 $$$v$$$ 的最短路径包含节点 $$$u$$$,以及两个端点位于两个此类节点之间的所有边。

您有兴趣查找 $$$f(S(n)), f(S(n-1)), \ldots, f(S(1))$$$。然而,有一个神奇的神谕向您隐藏了有关这棵树的信息!具体来说,预言机仅在读取 $$$f(S(x+1))$$$ 的结果后才告诉你有关顶点 $$$x$$$ 的信息。换句话说,你必须在线解决这个问题,从节点$$$n$$$开始,到节点$$$1$$$结束。

$$$^{\text{*}}$$$树是没有环的连通图。 有根树是一棵树,其中一个顶点是特殊的,称为根。 顶点 $$$v$$$ 的父顶点是从 $$$v$$$ 到根的简单路径上的第一个顶点。根没有父级。 顶点 $$$v$$$ 的子节点是任何以 $$$v$$$ 为父节点的顶点 $$$u$$$。

$$$^{\text{†}}$$$这里,$$$\gcd(x, y)$$$表示整数$$$x$$$和$$$y$$$的最大公约数(GCD)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) – 表示树中的节点数。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 行将包含有关节点 $$$j=n-i+1$$$ 的信息,格式如下。

  • $$$a_j \; k \; c_1 \; c_2 \; \l点\; c_k$$$:节点 $$$j=n-i+1$$$ 具有关联值 $$$a_j$$$ 和带有节点标签 $$$c_1,c_2,\ldots,c_k$$$ 的 $$$k$$$ 子节点。

对于每个节点 $$$j$$$,保证 $$$2 \le a_j \le 10^{18}$$$ 和 $$$j+1 \le c_i \le n$$$。

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

保证一个测试用例中所有节点的 $$$k$$$ 之和恰好为 $$$n-1$$$,并且边形成一棵有效的有根树。

输出

对于每个测试用例,您必须输出 $$$n$$$ 行,其中第 $$$i$$$ 行包含 $$$f(S(n-i+1))$$$ 的值。

请注意,此问题在技术上是交互式的。具体来说,交互器只有在读取您的输出行后才会为您提供下一条信息。

打印每个后 线,您必须输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

$$$^{\text{*}}$$$要刷新,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • sys.stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

4
5
11 0
7 0
5 0
3 2 4 5
2 2 2 3
5
10 0
8 0
6 0
4 0
2 4 2 3 4 5
6
221 0
143 1 6
77 1 5
35 1 4
15 1 3
6 1 2
3
1000000000000000000 0
999999999999999998 0
999999999999999998 2 3 2

输出
复制

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

注意

在第一个测试用例中,由于 $$$a_i$$$ 的所有值都是互质的,因此每条路径不可能覆盖多个节点。因此,$$$f(S(1))$$$ 的值为$$$5$$$。

在第二个测试用例中,我们可以使用以下 $$$4$$$ 垂直路径验证 $$$f(S(1))=4$$$ :

  • $$$[1,2]$$$。这条垂直路径的GCD是$$$\operatorname{gcd}(2,4)=2$$$。
  • $$$[3]$$$。这条垂直路径的GCD为$$$\operatorname{gcd}(6)=6$$$。
  • $$$[4]$$$。这条垂直路径的GCD为$$$\operatorname{gcd}(8)=8$$$。
  • $$$[5]$$$。这条垂直路径的GCD为$$$\operatorname{gcd}(10)=10$$$。

由于没有垂直路径的 GCD 为 $$$1$$$,因此该解决方案是有效的。此外,我们可以证明不可能用少于 $$$4$$$ 垂直路径覆盖所有节点。