← 返回题目列表

Codeforces · 1670/E

E. 树上的 Hemose

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

经过上一届地区赛,Hemose和他的队友们终于获得了ICPC世界总决赛的参赛资格,所以为了这个伟大的成就和他对树木的热爱,他给大家这个问题作为他团队的名字“Hemose 3al shagra”(树上的Hemose)。

给你一棵有 $$$n$$$ 个顶点的树,其中 $$$n$$$ 是 $$$2$$$ 的幂。您必须为每个节点和边指定 $$$[1,2n -1]$$$(含)范围内的整数值,其中所有值都是不同的。

为每个节点和边赋予一个值后,您应该为树选择一些根,以便最小化从根开始到任何节点或边结束的任何简单路径的最大成本。

两个节点 $$$u$$$ 和 $$$v$$$ 之间或任何节点 $$$u$$$ 和边 $$$e$$$ 之间的路径成本定义为它们之间的所有节点和边值(包括端点)的按位异或(请注意,在树中,两个节点之间或节点与边之间只有一条简单路径)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5\cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$p$$$ ($$$1 \le p \le 17$$$),其中 $$$n$$$ (树中的顶点数)等于 $$$2^p$$$。

接下来的 $$$n−1$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$) 意味着树中的顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。

保证给定的图是一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot 10^5$$$。

输出

对于第一行的每个测试用例,打印所选的根。

在第二行,打印 $$$n$$$ 个由空格分隔的整数,其中第 $$$i$$$ 个整数表示第 $$$i$$$ 个节点的选定值。

在第三行,打印由空格分隔的 $$$n-1$$$ 整数,其中第 $$$i$$$ 个整数表示第 $$$i$$$ 条边的选定值。边缘按照其在输入数据中出现的顺序进行编号。

如果有多个解,则可以输出任意一个。

示例

输入 #1

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

输出 #1

3
5 1 3 6
4 2 7
5
1 2 8 11 4 13 9 15
6 14 3 7 10 5 12

注意

第一个测试用例中的树以及所有节点和边的权重如图所示。

所有路径的成本为:

- $$$3$$$;
- $$$3\oplus 7=4$$$;
- $$$3\oplus 7\oplus 6=2$$$;
- $$$3\oplus 2=1$$$;
- $$$3\oplus 2\oplus 1=0$$$;
- $$$3\oplus 2\oplus 1\oplus 4=4$$$;
- $$$3\oplus 2\oplus 1\oplus 4\oplus 5=1$$$。

所有这些路径的最大成本为 $$$4$$$。我们可以证明,不可能通过不同的方式分配值和选择根来实现所有路径的较小最大成本。

第二个测试用例中的树: