【Codeforces 566E】Restoring Map
构造，bitset
题目大意：
给定一棵树，对每个结点，告诉你离它距离不超过 $2$ 的所有点，包括本身，要求构造一棵符合条件的树。
给出结点的顺序乱序（不告诉你这是哪个点只告诉你离它距离不超过 $2$ 的点有哪些）。每个结点给出的距离其不超过 $2$ 的结点也乱序。
题解：
构造。
令每个点，离它距离不超过 $2$ 的那些点形成一个集合。
考虑两个距离为 $3$ 的点，它们的集合中，有且仅有两个点重复，即夹在它们中间的点。这两个点之间显然有边。
通过bitset求交集，我们可以 $O(\frac{n^3}\omega)$ 搞出这些连边。
但这不是所有的边。发现这样求出的边都只连接了非叶子结点。我们要把剩下的叶子结点也连上去。
有两个特殊情况：
- 只确定了两个非叶子结点。那么剩下的叶子结点只可能连在这两个结点上，且一侧的叶子结点是确定的（中间两个非叶子是可以互换的，不影响答案）。特判掉即可。
- 一个非叶子结点都没有确定，这种情况表示数的直径长度小于 $3$。那么随便输出一棵菊花树就好了。
除去了这两种情况，剩下的情况中，非叶子结点的个数都大于等于 $3$。
我们对每个非叶子结点，求出距离其不超过 $1$ 的非叶子结点形成的集合。在特判掉特殊情况后，每个点的集合都是不同的。
考虑如何确定一个叶子结点的父亲。我们假设已经确定了距离这个结点不超过 $2$ 的集合是哪个。我们先把这个集合中的叶子结点删掉，那么这个非叶子结点的集合，和距离它父亲不超过 $1$ 的非叶子结点形成的集合是完全相等的。由于后者唯一对应一个结点，这样的方法就可以求出父亲。复杂度 $O(\frac{n^3}\omega)$。
现在就是要确定一个叶子结点的那个集合是哪个了。我们找到所有包含该叶子结点的集合，有四种情况：
- 该叶子结点所属集合。
- 该叶子结点的兄弟叶子结点所属集合。
- 该叶子结点父亲所属集合。
- 与该叶子结点的父亲相连的非叶子结点所属集合。
其中，$1$ 和 $2$ 的集合是完全一样的，可以忽略。$3$ 的结点个数一定严格多于 $1$（去掉之前的特殊情况后，一定存在一个到非叶子结点为 $2$，到叶子结点为 $3$ 的非叶子结点）。$4$ 的结点个数也严格多于 $1$，分析方式与 $3$ 类似。
即我们找到一个包含当前叶子结点的，并且包含的结点个数最少的集合，就是这个叶子结点的集合。然后确定父亲即可。
时间复杂度 $O(\frac{n^3}\omega)$。
Code：
#include<iostream>
#include<bitset>
#include<vector>
#include<cstring>
const int N=1002;
using namespace std;
typedef bitset<N>BitSet;
BitSet b[N],r[N],bt,vis;
int n,c[N];
bool e[N][N];
vector<int>G[N];
inline void addedge(int u,int v){
G[u].push_back(v),G[v].push_back(u);
}
void DFS(int u,bool tg,BitSet&b){
b.set(u);
if(!tg)for(int i:G[u])DFS(i,1,b);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1,x,y;i<=n;++i)
for(cin>>x,c[i]=x;x--;){
cin>>y,b[i].set(y);
}
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j){
bt=b[i]&b[j];
if(bt.count()==2){
int u=bt._Find_first();
bt.reset(u);
int v=bt._Find_first();
addedge(u,v);
vis[u]=vis[v]=1;
}
}
for(int i=1;i<=n;++i)
if(vis[i])DFS(i,0,r[i]);
if(vis.count()==2){
int u=vis._Find_first();
vis.reset(u);
int v=vis._Find_first();
BitSet s,t;
for(int i=1;i<=n;++i)
if(b[i].count()!=n){
if(!s.count()||b[i]!=s)s=b[i];else t=b[i];
}
for(int i=1;i<=n;++i)
if(i!=u&&i!=v){
if(s.test(i))addedge(i,u);else addedge(i,v);
}
}else
if(vis.count()==0){
for(int i=2;i<=n;++i)addedge(1,i);
}else{
for(int i=1;i<=n;++i)if(!vis[i]){
int ct=n,id=0;
for(int j=1;j<=n;++j)
if(b[j].test(i)&&c[j]<ct)ct=c[j],id=j;
bt=b[id];
for(int i=1;i<=n;++i)
if(!vis[i])bt.reset(i);
for(int j=1;j<=n;++j)
if(vis[j]&&bt==r[j]){addedge(i,j);break;}
}
}
for(int i=1;i<=n;++i)
for(int j:G[i])
if(!e[i][j])cout<<i<<' '<<j<<'\n',e[i][j]=e[j][i]=1;
return 0;
}