链接：https://www.luogu.com.cn/problem/CF566E
题目描述：有一个\(n\)个节点的树，你得到了\(n\)条关于每个点信息，每条信息记录了距离某一个点小于等于\(2\)的所有点，但你不知道每条信息具体是哪个点的，你需要构造一棵满足这些信息的树。
数据范围：\(n<=1000\)
题解：对于这个题，我们可以发现一些性质：
性质\(1\):若对于非叶节点\(x,y\)，若这些信息之间的交有\({x,y}\)，则\(x,y\)之间有边。(由此也可判\(x,y\)是否是叶子节点)
证明:对\(x\)扩展不为\(y\)的点\(u\)，对\(y\)扩展不为\(x\)的点\(v\),则画图可知\(u,v\)点集交为\({x,y}\)，而若它们间无边，那么它们不能同时分配到一个大小为\(2\)的点集中。
性质\(2\):叶子节点的集合是包含它的最小点集。
证明:考虑叶子节点的父亲节点的父亲节点\(x\)，所有叶子走两步能到的节点都能被\(x\)所走到，而当\(x\)的走到的点与叶子节点相同，则它们刚好"对称",随便放都可以。
性质\(3\):当非叶节点个数\(>=2\)时，叶子节点集合的非叶子节点之间居中的那个点是它的父亲节点。
证明：首先\(dep\)居中的是合法的，那么需证明有且仅有一个，而当有两个合法的点时，有一个点的集合会包含与它距离\(3\)的点，则矛盾。
当非叶节点个数为\(0,2\)时要特判，其余情况可用上述性质构造方案
#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9')
c=getchar();
while ('0'<=c&&c<='9')
sum=sum*10+c-'0',c=getchar();
return sum;
}
int n,cnt,x;
bitset<1000>p[1001];
bitset<1000>T;
bitset<1000>R[1001];
bitset<1000>F[1001];
bool S[1001][1001];
int fa[1001];
bool vis[1001],used[1001];
int color[1001],rt[1001];
int main()
{
int t;
n=read();
for (int i=1;i<=n;++i)
{
t=read(),cnt+=t;
while (t--)
x=read(),p[i][x]=1;
}
if (cnt==n*n)
{
for (int i=2;i<=n;++i)
printf("%d %d\n",1,i);
return 0;
}
int st,ed,len=0;
for (int i=1;i<=n;++i)
for (int j=i+1;j<=n;++j)
if ((p[i]&p[j]).count()==2)
T=p[i]&p[j],st=T._Find_first(),ed=T._Find_next(st),F[st][ed]=1,F[ed][st]=1,used[st]=1,used[ed]=1;
for (int i=1;i<=n;++i)
if (used[i])
F[i][i]=1;
for (int i=1;i<=n;++i)
for (int j=i+1;j<=n;++j)
if (used[i]&&used[j]&&F[i][j])
printf("%d %d\n",i,j),len++;
int res,miner;
for (int i=1;i<=n;++i)
if (!used[i])
{
res=1e9,miner=-1;
for (int j=1;j<=n;++j)
if (p[j][i]&&p[j].count()<res)
res=p[j].count(),miner=j;
R[i]=p[miner];
if (len!=1)
{
for (int j=1;j<=n;++j)
if (!used[j])
R[i][j]=0;
}
}
if (len==1)
{
for (int i=1;i<=n;++i)
for (int j=1;j<=i;++j)
if (!used[i]&&!used[j]&&R[i][j])
{
S[j][i]=1;
break;
}
for (int i=1;i<=n;++i)
if (!used[i]&&S[i][i])
{
if (st)
{
for (int j=1;j<=n;++j)
if (S[i][j])
printf("%d %d\n",st,j);
st=0;
}
else
{
for (int j=1;j<=n;++j)
if (S[i][j])
printf("%d %d\n",ed,j);
}
}
return 0;
}
for (int i=1;i<=n;++i)
{
for (int j=1;j<=n;++j)
if (!used[i]&&used[j]&&F[j]==R[i])
printf("%d %d\n",i,j);
}
return 0;
}