[CF566E] Restoring Map

Restoring Map
星空蚁来了秒了。
人与人的智力是有差距的。
刷再多的CF智力不行就是不行。
OI这种需要智力的游戏不适合我。
我还是更适合对智力要求低一点的。
比如和妹子贴贴。
但是也没有妹子。
life is hard.
这类树的构造似乎可以从边缘情况想起,比如 CF1844G
但是这个题从叶节点(称为2类点)开始想就寄了。
我们把点 x 的集合称为 \(S_x\)
考虑观察非叶节点(称为1类点)是否直接连边的性质,称直接相连的两点为 x,y。
那么我们可以找出一条形如 a-x-y-b 的链,则 \(S_a\cup S_b=\left\{x,y\right\}\)
不难证明该条件充要。
对于1类点个数 \(\geq\) 3个的,我们可以把所有1类点找出来,这些点首先需要连边。
再考虑所有2类点,其能连到的1类点为其父亲和爷爷,找出集合包含当前2类点的那个即可(如果都有就随便,这说明两者父子关系不定)
对于只有1个1类点,构造一个菊花图即可。
对于2个1类点,这时所有2类点分成两部分,相同集合的必须连同一个点,这个也很好判断。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
#define mp make_pair
#define db double
#define ll long long
#define ull unsigned long long
#define ld long double
#define b1t bitset
typedef pair<int,int> kk;
void read(int &x){
	x=0;int f=1;char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<3)+(x<<1)+(s^48);s=getchar();
	}
	x*=f;
}
const int MAXN=1005;
int n;
b1t<MAXN> a[MAXN],b[MAXN],ye;
bool pd,vis[MAXN];
vector<kk> res;
int main(){
	read(n);
	pd=1;
	for(int i=1,op,x;i<=n;i++){
		read(op);
		pd&=(op==n);
		while(op--)
			{read(x);
			a[i][x]=1;
		}
	} 
	if(pd){
		for(int i=2;i<=n;i++) printf("%d %d\n",1,i);
		return 0;
	} 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			b1t<MAXN> tmp=a[i]&a[j];
			if(tmp.count()==2){
				int x=tmp._Find_first(),y=tmp._Find_next(x);
				if(b[x][y]) continue;
				b[x].set(y);b[y].set(x);ye[x]=ye[y]=1;
				b[x][x]=b[y][y]=1;res.push_back(mp(x,y));
			}
		}
	}
	if(ye.count()==2){
		int o1=0,o2=0;
		for(int i=1;i<=n;i++){
			if(ye[i]){
				if(!o1) o1=i;
				else{
					o2=i;break;
				}
			}
		}
		for(int i=1;i<=n;i++){
			if(a[i].count()<n){
				for(int j=1;j<=n;j++){
					if(!ye[j]&&a[i][j]) vis[j]=1;
				}
				break;
			}
		}
		for(int i=1;i<=n;i++) if(!ye[i]){
			if(vis[i]) res.push_back(mp(o1,i));
			else res.push_back(mp(o2,i));
		}
		for(auto u:res) printf("%d %d\n",u.first,u.second);
		return 0;
	}
	for(int i=1;i<=n;i++){
		pd=1;
		for(int j=1;j<=n;j++){
			if((a[i]&a[j])==a[j]&&a[i]!=a[j]){pd=0;break;}
		}
		if(!pd) continue;
		b1t<MAXN> tmp=a[i]&ye;
		for(int j=1;j<=n;j++){
			if(tmp[j]&&b[j]==tmp){
				if(!vis[j]){
					for(int k=1;k<=n;k++){
						if(!ye[k]&&a[i][k]) res.push_back(mp(j,k));
					}
					vis[j]=1;
				}
				break;
			}
		}
	}
	for(auto u:res) printf("%d %d\n",u.first,u.second);
	return 0;
}