思路
构造 \(k\) 个集合,使这些集合满足以下性质:
-
集合的并集为 \(V\)。
-
对于树 \(s\) 中的任意一条边 \((a,b)\),都能在 \(k\) 个集合中找到一个集合 \(x\) 使得 \(a,b\in x\)。
-
对于树 \(s\) 中的任意一个点 \(a\),所有在 \(k\) 个集合中包含了 \(a\) 的集合构成了一个连通块。
构造出来的价值为最大集合的大小。需要求出满足在价值最小的前提下,集合个数最少。
我们再把以上性质和要求进一步结合起来看,就不难发现这几个性质:
-
每个集合大小都应为 \(2\)。
-
每个集合其实就是就是原树的一条边。
如果要把这 \(k\) 个集合连接起来,所以那就应保证是相邻的两个边连接。
具体如何处理呢,很自然的我们会想到用邻接表进行处理,因为在邻接表重,相邻的两个边就是 \(g_{i,j}\) 和 \(g_{i,j+1}\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read();
int n;
vector<int> g[N];
int main()
{
n=read();
printf("%d\n",n-1);
for(int i=1;i<n;i++)
{
int a,b;
a=read();b=read();
printf("2 %d %d\n",a,b);
g[a].push_back(i);
g[b].push_back(i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<g[i].size()-1;j++)
{
printf("%d %d\n",g[i][j],g[i][j+1]);
}
}
return 0;
}
inline int read()
{
int x=0,f=1;
char ch;
ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-') f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')
{
x=(x<<1)+(x<<3)+(ch&15);
ch=getchar();
}
return x*f;
}
标签:int,题解,read,CF237D,邻接,集合
From: https://www.cnblogs.com/yzxgg/p/solution-cf237d.html