题解：P7966 [COCI 2021/2022 #2] Hiperkocka

· · 题解

首先相信大家都发现了得满分要求每条边都被选入某棵树。

从菊花入手，此时等价于选出 2^{n-1} 个数使得他们两两之间相差至少两个二进制位。只需要选出所有 \mathrm{popcount} 为偶数的数即可。

再考虑一般情况，换个角度理解题意，就是对于每条边 (x,y) 能找出它是哪棵树的哪条边。

尝试将这个定位逻辑简单化，那么由 x 和 y 得出的一个简单信息是 x 与 y 在哪一位不同，设为 i，那么我们可以规定它被定位到某棵树的第 i 条边上。

这也就是给 T 的每条边赋一个互不相同的 0 至 n-1 的边权（顺序随意），要求结果中每个 T 的相邻两点间相差的位就是边上的边权，即对于每个 1\le i\le 2^{n-1} 有 \forall u,v,(u,v)\in T: a_{i,u}\oplus a_{i,v}=2^{e_(u,v)}，其中 e 为所赋的边权。

于是此时我们只用确定 a_{i,0} 整个 a_i 序列就确定了。只需考虑怎么给每个 a_{i,0} 赋值。

考虑什么时候两棵树的两条边会冲突。

那么若 T_1 和 T_2 都含有边 (x,y)，则 (x,y) 在 T_1 和 T_2 的边权必然相同（为 \log_2(x\oplus y)），也即它们是 T 上的同一条边。

我们将树按从根向叶子的方向定向，则若 (x,y) 在 T_1 和 T_2 中的方向相同，可以倒推出 T_1 和 T_2 的根节点权值相同，矛盾。

因此只有当 (x,y) 在 T_1 中是 x\rightarrow y 而在 T_2 中是 y\rightarrow x 时有可能冲突，此时可以推出 T_1 和 T_2 的根节点的权值恰相差一个二进制位 e_{(x,y)}。

rt_1 \xrightarrow{c_1} \ \xrightarrow{c_2} \dots \xrightarrow{c_m} x \xleftrightarrow{e_{(x,y)}} y \ \xleftarrow{c_m} \dots \xleftarrow{c_2} \ \xleftarrow{c_1} rt_2

于是沿用菊花的做法，令每个根的节点都是 \mathrm{popcount} 为偶数的数即可。

代码 500B。

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
constexpr int N=55;
int n,a[N],cnt; vector<int> to[N];
void dfs(int u,int pa) { for(int v:to[u]) if(v!=pa) a[v]=a[u]^(1<<(cnt++)), dfs(v,u); }
int main(){
    cin>>n; For(i,1,n) { int x,y; cin>>x>>y; to[x].push_back(y); to[y].push_back(x); }
    dfs(0,-1); cout<<(1<<(n-1))<<'\n';
    For(s,0,(1<<n)-1) if(__builtin_parity(s)) For(i,0,n) cout<<(s^a[i])<<" \n"[i==n];
    return 0;
}