CF2106G2 Baudelaire (hard version)

这是该问题的困难版本。两个版本之间的唯一区别在于，在困难版本中树的形态可以是任意的。 本题是交互题。 波德莱尔非常富有，因此他购买了一棵大小为 $n$ 的树，这棵树以某个任意节点为根。此外，每个节点的值为 $1$ 或 $-1$。 书呆子牛看到了这棵树并爱上了它。然而计算机科学的收入不足以让他买下这棵树。波德莱尔决定和书呆子牛玩一个游戏，如果他赢了，就把这棵树送给他。 书呆子牛不知道哪个节点是根，也不知道节点的值。但他可以向波德莱尔提出两种类型的查询： 1. `1 k u₁ u₂ ... uₖ`：设 $f(u)$ 为从树的根到节点 $u$ 的路径上所有节点的值之和。书呆子牛可以选择一个整数 $k$（$1 \le k \le n$）和 $k$ 个节点 $u_1, u_2, ..., u_k$，然后他会收到值 $f(u_1) + f(u_2) + ... + f(u_k)$。 2. `2 u`：波德莱尔将切换节点 $u$ 的值。具体来说，如果 $u$ 的值为 $1$，则变为 $-1$，反之亦然。 如果书呆子牛在总共 $n + 200$ 次查询内正确猜出每个节点的值（即执行查询后树的最终值），他就获胜。你能帮助他获胜吗？

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^3$），表示树的大小。 接下来的 $n-1$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \neq v$），表示树中节点 $u$ 和 $v$ 之间有一条边。 保证所有测试用例的 $n$ 之和不超过 $10^3$，并且每个输入的图都是合法的树。

要提出类型 $1$ 的查询，请按以下格式输出一行（不带引号）： - `? 1 k u₁ u₂ ... uₖ`（$1 \le k, u_i \le n$） 评测机将返回一个整数，即 $f(u_1) + f(u_2) + ... + f(u_k)$。 要提出类型 $2$ 的查询，请按以下格式输出一行： - `? 2 u`（$1 \le u \le n$） 评测机会切换节点 $u$ 的值：如果其值为 $1$，则变为 $-1$，反之亦然。 当你找到答案时，请按以下格式输出一行： - `! v₁ v₂ ... vₙ`（$v_i = 1$ 或 $v_i = -1$，$v_i$ 是执行查询后节点 $i$ 的值） 之后，继续处理下一个测试用例，或者如果是最后一个测试用例则终止程序。输出答案不计入查询次数。 交互器不是自适应的，这意味着树的值在参与者提出查询之前就已经确定。 如果你的程序进行了超过 $n + 200$ 次查询，它应立即终止并收到 Wrong Answer 的判定。否则，你可能会得到任意判定，因为你的解决方案将继续从已关闭的流中读取数据。 在打印查询后，不要忘记输出换行符并刷新输出缓冲区。否则，你可能会得到 Idleness Limit Exceeded 的判定。可以使用以下方法刷新输出： - C++：`fflush(stdout)` 或 `cout.flush()` - Java：`System.out.flush()` - Pascal：`flush(output)` - Python：`stdout.flush()` - 其他语言请参考相关文档。 ## Hack 格式 对于 Hack 攻击，请使用以下格式： 第一行应包含一个整数 $t$（$1 \le t \le 100$）——测试用例的数量。 每个测试用例的第一行必须包含两个整数 $n$ 和 $root$（$2 \le n \le 10^3$，$1 \le root \le n$）——树的大小和树的根节点。 每个测试用例的第二行必须包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$|a_i| = 1$）——其中 $a_i$ 是节点 $i$ 的值。 接下来的 $n-1$ 行每行必须包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$）——表示节点 $u$ 和 $v$ 之间有一条边。 所有测试用例的 $n$ 之和不得超过 $10^3$，并且每个输入的图必须是合法的树。

在第一个示例中，树的根是节点 $4$，初始值为 $[-1, -1, -1, 1]$（第 $i$ 个值是节点 $i$ 的值）。 初始时，$f(1) = 0$，$f(2) = 0$，$f(3) = -1$，$f(4) = 1$。因此，第一个查询的答案是 $f(1) + f(2) + f(4) = 1$，第二个查询的答案是 $f(3) + f(1) = -1$。 在切换节点 $4$ 的值后，值变为 $[-1, -1, -1, -1]$。此时 $f(1) = -2$，$f(2) = -2$，$f(3) = -3$，$f(4) = -1$。因此 $f(1) + f(2) + f(4) = -5$，$f(3) + f(1) = -5$。 我们最终回答节点的值为 $[-1, -1, -1, -1]$，这是正确的。注意我们报告的是节点在变化后的值，而不是之前的值。 在第二个示例中，树的根是 $2$，初始值为 $[1, 1]$。 在最后一个示例中，树的根是 $1$，初始值为 $[-1, 1, 1, 1, 1, 1, -1]$。 注意这只是一个解释查询如何工作的示例，并不涉及具体的解题策略。 翻译由 DeepSeek V3 完成