正题

题目链接:https://www.luogu.com.cn/problem/CF566E

题目大意

有一棵树，但是你不知道它的形态。你现在只知道距离每个点距离不超过\(2\)的点集，但是你不知道每个点集是对应哪个点的。

现在要你求这棵树。

\(2\leq n\leq 1000\)

解题思路

考虑这样一种情况

那么\(?\)和\(?'\)的交集恰好是\(x\)和\(y\)，也就是所有非叶子的连边我们都可以用以上方式确定。

然后考虑怎么确定叶子的连边，对于叶子\(x\)来说，包含它的集合中最小的那个肯定是它自己的集合。

这样我们就可以确定每个叶子对应的集合了，然后考虑怎么求它的父亲。

会发现我们如果把叶子的集合中的叶子去掉，那就只剩下它的父节点和它父节点连接的其他非叶子节点。

我们再处理出一个非叶子节点连边的集合，然后一个一个比较就可以找到这个点的父亲了。

然后要特判一些情况：

1. 没有非叶子节点：此时\(n=2\)直接特判。
2. 只有一个非叶子节点：此时随便找一个点都可以当非叶子节点。
3. 只有两个非叶子节点：此时叶子的集合分两种情况，分别对应不同的父节点就好了。

用\(bitset\)优化即可做到\(O(\frac{n^3}{\omega})\)

code

#include
#include
#include
#include
#include
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=1050;
int n,k[N],f[N];;
bitset b[N],g[N],c,v;
vector >e;
int main()
{
	scanf("%d",&n);
	for(int i=0;i