LONELINESS WILL SHINE

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

相同的边之间两两不同，证明也简单，由于根取值不同，经过到根链上一路异或得到的点权也不同，得证。

代码很短。

CPP

#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;
}

文章操作

相关推荐

评论

LONELINESS WILL SHINE