← 返回题目列表

Codeforces · 2106/G2

G2. 波德莱尔(硬版)

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

这是问题的硬版本。这两个版本之间的唯一区别是,在硬版本中,树可以是任何形状。

这个问题是交互式的。

波德莱尔非常富有,所以他买了一棵大小为 $$$n$$$ 的树,根植于任意节点。此外,每个节点的值为 $$$1$$$ 或 $$$-1$$$。

书呆子牛看到了这棵树并爱上了它。然而,计算机科学给他的报酬不够,所以他买不起。波德莱尔决定和书呆子牛玩一场游戏,如果他赢了,他就会把这棵树送给他。

牛,书呆子不知道哪个节点是根,也不知道节点的值。然而,他可以向波德莱尔询问两种类型的问题:

  • $$$1$$$ $$$k$$$ $$$u_1$$$ $$$u_2$$$ $$$...$$$ $$$u_k$$$:令 $$$f(u)$$$ 为从树根到节点 $$$u$$$ 的路径中所有节点值的总和。 Cow the Nerd 可以选择一个整数 $$$k$$$ $$$(1 \le k \le n)$$$ 和 $$$k$$$ 节点 $$$u_1, u_2, ..., u_k$$$,他将收到值 $$$f(u_1) + f(u_2) + ... + f(u_k)$$$。
  • $$$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_1$$$ $$$u_2$$$ $$$...$$$ $$$u_k$$$", ($$$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_1,v_2,...,v_n$$$” ($$$v_i = 1$$$ 或 $$$v_i = -1$$$,$$$v_i$$$ 是执行查询后节点 $$$i$$$ 的值)

之后,继续处理下一个测试用例,如果是最后一个测试用例则终止程序。打印答案不算作查询。

交互器是 不 自适应,意味着在参与者提出查询之前树的值是已知的。

如果您的程序进行超过 $$$n + 200$$$ 查询,您的程序应立即终止以接收判决 错误答案。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印查询后,不要忘记输出行尾并刷新输出。否则,您可能会得到 超出空闲限制 判决。为此,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中
  • System.out.flush() 在 Java 中;
  • 冲洗(输出) 帕斯卡;
  • stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

黑客

对于 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$$$,并且提供的每个图必须是有效的树。

示例

输入
复制

3
4
1 4
4 2
2 3

1

-1


-5

-5

2
1 2

2

7
1 2
2 7
7 3
7 4
7 5
7 6

-1


输出
复制





? 1 3 1 2 4

? 1 2 3 1

? 2 4
? 1 3 1 2 4

? 1 2 3 1

! -1 -1 -1 -1


? 1 1 1

! 1 1






? 1 1 1

! -1 1 1 1 1 1 -1

注意

在第一个示例中,树的根是节点 $$$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]$$$。

请注意,这只是查询如何工作的解释,不应该使用任何特定策略来解决问题。