这是问题的硬版本。这两个版本之间的唯一区别是,在硬版本中,树可以是任何形状。
这个问题是交互式的。
波德莱尔非常富有,所以他买了一棵大小为 $$$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]$$$。
请注意,这只是查询如何工作的解释,不应该使用任何特定策略来解决问题。