CF1670E Hemose on the Tree

在上一次区域赛后，Hemose 和他的队友们终于晋级了 ICPC 世界总决赛。为了庆祝这一伟大成就以及他对树的热爱，他以自己队伍的名字 “Hemose 3al shagra”（Hemose on the tree）为题，给你出了这道题。 给定一棵有 $n$ 个节点的树，其中 $n$ 是 $2$ 的幂。你需要为每个节点和每条边分配一个整数值，范围为 $[1,2n-1]$（包含端点），且所有值互不相同。 在为每个节点和边分配好数值后，你应选择树的某个节点作为根，使得从根出发到任意节点或边的所有简单路径的最大代价最小。 从节点 $u$ 到节点 $v$，或从节点 $u$ 到边 $e$ 的路径代价定义为路径上所有节点和边的数值的按位异或（bitwise XOR），包括起点和终点（注意，在树中，任意两节点或节点与边之间只有唯一一条简单路径）。

第一行包含一个整数 $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$ 条边的数值。边的编号按照输入顺序。 如果有多组解，输出任意一组均可。

第一组测试数据中，所有节点和边的权值分配如下图所示。  所有路径的代价为： - $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$。可以证明，无法通过不同的分配方式和根节点选择使所有路径的最大代价更小。 第二组测试数据的树如下图所示：  由 ChatGPT 4.1 翻译