题意理解

我们有一个 n 维超立方体 ( Q_n )，它有 ( 2^n ) 个顶点，编号 ( 0 ) 到 ( 2^n-1 )。
两个顶点之间有边当且仅当它们的编号异或的结果是 2 的幂（即二进制表示只有一位不同）。

我们还有一棵树 ( T )，它有 ( n+1 ) 个顶点（编号 0 到 n）和 ( n ) 条边。

我们要在 ( Q_n ) 中放置尽可能多的 ( T ) 的副本（同构嵌入），使得：

1. 每个副本的顶点对应到 ( Q_n ) 的不同顶点
2. 副本中相邻顶点在 ( Q_n ) 中也相邻
3. ( Q_n ) 的每条边至多被一个副本使用

目标是放置尽量多的副本，最多 ( 2^{n-1} ) 个（因为 ( Q_n ) 有 ( n \cdot 2^{n-1} ) 条边，每个副本用 ( n ) 条边，所以最多 ( 2^{n-1} ) 个副本）。

样例分析

样例 1

n=1，超立方体 Q1 有 2 个顶点 0-1。
树 T 有 2 个顶点 0-1。
只能放 1 个副本：0 1。

样例 2

n=2，Q2 是正方形 0-1-3-2（按格雷码顺序）。
树 T 是 0-1-2（一条链）。
可以放 2 个副本：

• 0 1 3
• 0 2 3
  它们覆盖了 Q2 的所有边。

样例 3

n=3，Q3 是立方体。
树 T 是星形，中心 0，叶子 1,2,3。
可以放 4 个副本，覆盖所有边。

思路

这是一个 边不交的树分解 问题。
已知 n 维超立方体可以分解为 ( 2^{n-1} ) 个这样的树（完全边覆盖）。

构造方法：
我们可以利用 超立方体的递归结构 和 对称性。

构造方法（归纳法）

1. n=1：Q1 就是一条边，树 T 也是一条边，直接放。

2. n=2：Q2 是 4 个点的环，但实际上是正方形。
   我们可以把 Q2 看作两个 Q1 之间加边连接。
   树 T 有 3 个顶点，n=2 时 T 是一条链 0-1-2。
   我们可以用两种方法放置，分别用不同的边。

3. n 维到 n+1 维：
   ( Q_{n+1} ) 可以看作两个 ( Q_n )（称为 A 和 B）之间对应的顶点相连（这些新边称为“跨维边”）。
   如果我们已经有 ( Q_n ) 的一个边不交的树分解，那么我们可以在 ( Q_{n+1} ) 中构造两倍的树：

   • 对每个在 ( Q_n ) 中的树副本，我们可以在 A 和 B 中各放一个修改版，并利用跨维边连接它们，形成 ( Q_{n+1} ) 中的树。

具体构造（格雷码坐标法）

更直接的方法：
将超立方体顶点用二进制表示，每条边是翻转某一位。
我们可以把顶点分成两部分：偶数和奇数 popcount（二进制中 1 的个数）。
树 T 是二分图吗？不一定，但超立方体是二分图（按 popcount 奇偶）。

已知结论：
n 维超立方体可以分解为 n 个完美匹配（每个匹配是翻转固定位的边）。
我们可以把 T 的 n 条边分配到不同的维度上，然后通过平移生成所有副本。

实现方法

1. 先找一个 T 在 Q_n 中的嵌入（一个副本）。
2. 利用超立方体的平移对称性（异或运算）生成所有副本：
   • 对每个副本的顶点集合整体异或一个常数，得到新的副本。
   • 如果初始副本选择得当，这些平移后的副本边不交。

关键：初始副本要满足它的每条边属于不同的完美匹配（维度），这样平移后才不会冲突。

构造步骤（以代码形式）

我们可以这样构造：

• 把树 T 的 n 条边分别映射到超立方体的 n 个维度上。
• 选择一个根节点（比如 0），然后通过 BFS 给树 T 的每个节点分配超立方体顶点，使得每条边对应一个维度翻转。
• 这样构造的初始副本，每条边属于不同的完美匹配。
• 然后对所有的偶数 popcount 的顶点（或所有顶点的一半）进行平移，得到 ( 2^{n-1} ) 个边不交的副本。

代码实现

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
vector<pair<int, int>> tree_edges; // 树的边
vector<int> tree_adj[17];         // 树的邻接表
int dim[17][17];                  // 树边对应的维度
int node_map[17];                 // 树节点 -> 超立方体顶点
bool used[1 << 16];               // 超立方体顶点是否已用（初始时不用，平移时用）
int popcount[1 << 16];

void dfs_map(int u, int parent, int cur) {
    node_map[u] = cur;
    for (int v : tree_adj[u]) {
        if (v == parent) continue;
        int d = dim[u][v];
        dfs_map(v, u, cur ^ (1 << d));
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        tree_edges.push_back({x, y});
        tree_adj[x].push_back(y);
        tree_adj[y].push_back(x);
    }

    // 为树的每条边分配一个维度
    for (int i = 0; i < n; i++) {
        int u = tree_edges[i].first;
        int v = tree_edges[i].second;
        dim[u][v] = i;
        dim[v][u] = i;
    }

    // 初始映射：节点0映射到超立方体顶点0
    dfs_map(0, -1, 0);

    // 计算popcount
    for (int i = 0; i < (1 << n); i++) {
        popcount[i] = __builtin_popcount(i);
    }

    // 输出副本数
    cout << (1 << (n - 1)) << endl;

    // 生成所有副本：对偶popcount的顶点进行平移
    for (int trans = 0; trans < (1 << n); trans++) {
        if (popcount[trans] % 2 != 0) continue; // 只用偶popcount的平移
        for (int i = 0; i <= n; i++) {
            cout << (node_map[i] ^ trans) << " ";
        }
        cout << endl;
    }

    return 0;
}

正确性说明

• 初始副本中，每条边对应翻转不同的位，所以它们属于不同的完美匹配。
• 平移时，偶 popcount 的平移不会改变边的所属匹配（因为异或运算保持维度）。
• 因此所有副本边不交，且覆盖所有边（因为每个匹配的所有边都被覆盖一次）。

复杂度

• 顶点数 ( 2^n )，但 ( n \le 16 )，所以可行。
• 输出大小 ( 2^{n-1} \times (n+1) ) 在范围内。

这样我们就能得到满分构造。