CF2211E Minimum Path Cover

尽管题目名称可能暗示了什么，我们仍希望这道题实际上不是 NP-hard。 本题为交互题。 给定一棵大小为 $m$ 的有根树 $T$，每个节点 $i$ 关联一个值 $a_i$，定义一条垂直路径为一系列节点 $[s_1,s_2,\ldots,s_p]$，满足对所有 $1 \leq i < p$，有 $s_{i+1}$ 是 $s_i$ 的儿子。如果这条路径上的所有 $a_{s_j}$ 的最大公约数 $\operatorname{gcd}(a_{s_1},a_{s_2},\ldots,a_{s_p}) \neq 1$，则称这条垂直路径为“好路径”。定义 $f(T)$ 为覆盖整棵树所有节点且每个节点恰好在一条好路径中的最少好路径数。 现在有一颗奇怪的有根树，包含 $n$ 个节点，节点 $1$ 为根。树满足每个节点的所有儿子编号都比本节点大。记 $S(u)$ 为以 $u$ 为根的子树，即包括所有在 $1$ 到 $v$ 的最短路径经过 $u$ 的节点 $v$，以及其间所有相关边。 你需要按顺序在线求出 $f(S(n))$, $f(S(n-1))$, ..., $f(S(1))$。但是，有一个神奇的“oracle”会隐藏部分树的信息：只有你给出 $f(S(x+1))$ 后，才能获得节点 $x$ 的所有信息。因此你必须从节点 $n$ 向节点 $1$ 依次在线解答。 一棵树是一个无环连通图。有根树是指指定了一个根节点的树。对任意节点 $v$，其父亲为从 $v$ 到根的路径上的第一个点。根节点没有父亲。$v$ 的儿子是父亲为 $v$ 的所有节点。 这里 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公因数，参见 [最大公因数(GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor)。

每个测试包含多组数据。第一行输入测试组数 $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 \; \ldots \; c_k$ ：节点 $j = n-i+1$ 的值为 $a_j$，有 $k$ 个儿子，分别为编号 $c_1,c_2,\ldots,c_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))$ 的值。 注意：本题为交互题。每输出一行后，交互器只会在收到你的本行输出后提供下一个节点的信息。 每输出一行后必须输出换行符并及时刷新输出缓冲区，否则会因超时被判“Idleness limit exceeded”。 刷新的方法如下： - 在 C++ 中使用 fflush(stdout) 或 cout.flush()； - 在 Python 中使用 sys.stdout.flush()； - 其它语言请参考官方文档。

在第一个测试用例中，由于所有 $a_i$ 互质，不可能有一条路径覆盖多个节点。因此 $f(S(1)) = 5$。 在第二个测试用例中，可以用 $4$ 条垂直路径覆盖所有节点，具体如下： - $[1,2]$，其 GCD 为 $\gcd(2,4)=2$。 - $[3]$，其 GCD 为 $\gcd(6)=6$。 - $[4]$，其 GCD 为 $\gcd(8)=8$。 - $[5]$，其 GCD 为 $\gcd(10)=10$。 由于每条路径的 GCD 都不为 $1$，这是一个合法方案。同时可以证明不能用更少的路径覆盖所有节点。 由 ChatGPT 5 翻译