原题链接

链式前向星，他来了

• 通过观察发现，每个集合的大小最小为 \(2\)，显然我们需要构造一种方案使得每一个集合的大小都为 \(2\)，这样是最优的。
• 每个集合大小为 \(2\)，等价于把每条边转换成新树上的一个点，一共 \(n-1\) 边，对应 \(n-1\) 个集合，每个集合的点对在 dfs 的时候输出每一条边的两个端点即可。
• 对于第三问，一种合法的构造方案是：
  • 对于一个节点 \(u\) 和它的儿子 \(v\)，让 \(\{u,v\}\) 与 \(\{fa_u,u\}\) 连边。注意根节点需要特殊处理，因为不存在 \(fa_{root}\)。
  • 具体操作是记录一个 \(id\)，表示 \(\{fa_u,u\}\) 的编号，用 dfs 实现编号的向下传递，每次在 \(id\) 和 \({\{u,v\}}\) 之间建边。
  • 对于根节点，我们让 \(id\) 初值为 \(0\)，并且在 \(id\) 为零的时候不进行加边操作，而是将 \(\{root,v\}\) 的编号赋值给 \(id\)，也就是将根节点和其他儿子组成的集合都与根节点和第一个儿子的集合连边，仍能保证第三条性质。

code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<utility>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
#define FOR(i,a,b) for(register int i=a;i<=b;i++)
#define ROF(i,a,b) for(register int i=a;i>=b;i--)
#define mp(a,b) make_pair(a,b)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
inline int read();
typedef long long ll;
typedef double db;
const int N=1e5+5;
const int INF=0x3f3f3f3f;
int n,m,k;
struct E{
	int to,nex;
}edge[N<<1];
int head[N],cnt=0;
void add(int u,int v){
	edge[++cnt]=(E){v,head[u]};
	head[u]=cnt;
}
void dfs(int u,int fa){
	for(int i=head[u];i;i=edge[i].nex){
		int v=edge[i].to;
		if(v==fa) continue;
		printf("2 %d %d\n",u,v);
		dfs(v,u);
	}
}
map<pii,int>pos;
int Pos=0;
int toNum(int u,int v){
	if(pos.find(mp(u,v))==pos.end()){
		pos[mp(u,v)]=++Pos;
	}
	return pos[mp(u,v)];
}
void dfs1(int u,int fa,int id){
	for(int i=head[u];i;i=edge[i].nex){
		int v=edge[i].to;
		if(v==fa) continue;
		if(id!=0) printf("%d %d\n",id,toNum(u,v));
		else id=toNum(u,v);
		dfs1(v,u,toNum(u,v));
	}
}
int main()
{
	n=read();
	FOR(i,1,n-1){
		int u=read(),v=read();
		add(u,v);
		add(v,u);
	}
	printf("%d\n",n-1);//第一问 
	dfs(1,0);//第二问 
	dfs1(1,0,0);//第三问 
	return 0;
}


inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f*x;
}