LONELINESS WILL SHINE

冷却心 · 2025-11-26 14:19:32 · 题解

Too hard。

从菊花入手，容易发现菊花的根取 x 的话，连出去的 n 个叶子应该分别为 x \oplus 2^i，i 完整遍历 0,\dots,n-1。注意到连出去的叶子和根 popcount 奇偶性不同，我们取所有 popcount 为偶数的点作为根跑出 2^{n-1} 棵树就是一个合法的解。能证明任意两条边都不同，原因是如果两条边异或的 2^i 不同则边显然不同，所以只考虑 i 相同的边，然而这些边都在不同的树上，由于根不同所以边的另一端也不同，得证。

考虑一般情况，沿用上面的做法，钦定 x 作为根，给 n 条边任意赋一个 0 到 n-1 的排列 p_1,\dots,p_n 作为权值，表示经过这条边到达子节点时点权要异或上 2^{p_i}，那么取所有 popcount 偶数的 x 作为根跑一遍得到的解就是合法的解。证明每条边都不同的方式基本一致，首先同一棵树上的边显然没有相同的，因为 p 值都不一样，并且不同树上 p_i 不同的边也一定不同，因为异或的幂不同，所以只需要证明 p_i 相同的边之间两两不同，证明也简单，由于根取值不同，经过到根链上一路异或得到的点权也不同，得证。

代码很短。

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 100;
vector<pair<int, int> > G[N];
int n, res[N];

void DFS(int u, int f, int s) {
    res[u] = s;
    for (auto [v, x] : G[u]) if (v != f) DFS(v, u, s ^ (1 << x));
}

int main() {
    freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 0, u, v; i < n; i ++)
        cin >> u >> v, G[u].push_back({v, i}), G[v].push_back({u, i});
    cout << (1 << (n - 1)) << "\n";
    for (int s = 0; s < (1 << n); s ++) if (__builtin_popcount(s) % 2 == 0) {
        DFS(0, 0, s);
        for (int i = 0; i <= n; i ++) cout << res[i] << " \n"[i == n];
    }
    return 0;
}