P7966 题解

· · 题解

首先每条边都要被选入一棵树中。

注意到如果令每条边的权值为两边的异或值，则对于每个 0\le i<n，权值为 2^i 的边恰有 2^{n-1} 条。而正好需要找 2^{n-1} 棵树，这说明可以使得每棵树中，边的权值取完所有 2^i，可以令每棵树对应位置的边权值相同。

考虑求出图中的一个最大独立集作为根集，可以证明这个独立集的大小为 2^{n-1}。这些根之间都至少差了两位，这样构造出来的树一定可以保证每条边都被选择了至多一次，这就是一个合法的解，时间复杂度 O(n2^n)，不知道为什么开 n\le 16。

代码极短：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 20

int n, ct; vector<int> e[MAXN]; int dis[MAXN], wfa[MAXN]; bool vis[65536]; vector<int> vec;

void dfs(int x, int f){for (auto i: e[x]) if (i ^ f) wfa[i] = 1<<(ct++), dis[i] = dis[x]^wfa[i], dfs(i, x);}

signed main(){
    // freopen("constr.in", "r", stdin); freopen("constr.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n; for (int i(1), u, v; i<=n; ++i) cin >> u >> v, e[u].push_back(v), e[v].push_back(u); dfs(0, -1); cout << (1<<(n-1)) << '\n';
    for (int i(0); i<(1<<n); ++i) if (!vis[i]){vec.push_back(i); for (int j(0); j<n; ++j) vis[i^1<<j] = 1;}
    for (auto i: vec){for (int j(0); j<=n; ++j) cout << (i^dis[j]) << ' '; cout << '\n';}

    return 0;
}