← 返回题目列表

Codeforces · 2106/G1

G1. 波德莱尔(简单版)

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

这是问题的简单版本。两个版本之间唯一的区别是,在这个版本中,保证每个节点都与节点$$$1$$$相邻。

这个问题是交互式的。

波德莱尔非常富有,所以他买了一棵大小为 $$$n$$$ 的树,该树以任意节点为根。此外,每个节点的值为 $$$1$$$ 或 $$$-1$$$。 在此版本中,每个节点都与节点 $$$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$$$ 之间的边。 在此版本中,保证 $$$u = 1$$$ 或 $$$v = 1$$$.

保证所有测试用例的 $$$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$$$,并且提供的每个图必须是有效的树。 对于此版本,每个节点必须与节点 $$$1$$$ 相邻.

示例

输入
复制

1
4
1 2
3 1
1 4

0


-6

输出
复制





? 1 3 1 2 3

? 2 2
? 1 3 1 2 3

! -1 -1 -1 1

注意

在示例中,树的根是节点 $$$2$$$,节点的值为 $$$[-1, 1, -1, 1]$$$。因此,$$$f(1) = 0、f(2) = 1、f(3) = -1、f(4) = 1$$$。

首先,我们查询 $$$f(1) + f(2) + f(3)$$$ 之和,因此我们收到值 $$$0$$$。然后,我们切换节点$$$2$$$的值,值为:$$$[-1, -1, -1, 1]$$$。因此,$$$f(1) = -2、f(2) = -1、f(3) = -3、f(4) = -1$$$ 和 $$$f(1) + f(2) + f(3) = -6$$$。

最后,我们计算出节点的值为 $$$[-1, -1, -1, 1]$$$,所以我们回答这个问题。

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