首页 > 其他分享 >题解:CF237D

题解:CF237D

时间:2023-10-16 23:35:14浏览次数:43  
标签:int 题解 read CF237D 邻接 集合

题目传送门

思路

构造 \(k\) 个集合,使这些集合满足以下性质:

  • 集合的并集为 \(V\)。

  • 对于树 \(s\) 中的任意一条边 \((a,b)\),都能在 \(k\) 个集合中找到一个集合 \(x\) 使得 \(a,b\in x\)。

  • 对于树 \(s\) 中的任意一个点 \(a\),所有在 \(k\) 个集合中包含了 \(a\) 的集合构成了一个连通块。

构造出来的价值为最大集合的大小。需要求出满足在价值最小的前提下,集合个数最少。

我们再把以上性质和要求进一步结合起来看,就不难发现这几个性质:

  1. 每个集合大小都应为 \(2\)。

  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

相关文章

  • 题解 P7468【[NOI Online 2021 提高组] 愤怒的小 N】
    题解P7468【[NOIOnline2021提高组]愤怒的小N】problem首先是有一个字符串\(S=\texttt{"0"}\),做无限次“将\(S\)的每一位取反接在\(S\)后面”的操作,形如\(S=0110100110010110\cdots\)。另外给一个\(k-1\)次多项式\(f\),求\(\sum_{i=0}^{n-1}S_if(i).\)\(n\leq......
  • 题解 ABC267F【Exactly K Steps】
    (accoders::NOI#5541.醉(intoxicated))题目描述Robin有一棵树,他有\(m\)次询问,每次询问他给你\(u,k\),你需要输出树上的一个节点\(v\)满足\(dist(u,v)=k\),或者报告无解。\(dist(u,v)\)表示树上\(u\)到\(v\)的最短路径的边数。\(n\leq10^5\)solution考虑求出每个......
  • Math teacher's homework 题解
    preface网上的题解看不懂,看代码看懂了:)solution考虑\(\mathrm{x_i}\)的倒数第\(\mathrm{low_i-1}\)位到倒数第\(\mathrm{1}\)位可以乱选(选\(\mathrm{0/1}\)都满足\(\mathrm{x_i\leqm_i}\)),那么就需要\(\mathrm{x_i}\)和\(\mathrm{m_i}\)的第\(\mathrm{1}\)位......
  • YACS 2023年9月月赛 甲组 题解
    题目链接1题目链接2题目链接3榜单终于公布了,这应该是第二长的榜单公布吧。(最长的一次是去年八月,拖到九月开始后才公布) T1是傻逼数据结构不说了吧,对于每个点枚举以他为角的$k\timesk$的四个正方形算一下点的数量,用$cdq$或者扫描线都行。看这个题目编号是$81$,看来是很......
  • 题解整理
    CF1740ACF1740BCF1740DCF1711BCF1253BCF1080BCF1237ACF1743ACF1743CCF1743BCF1370B......
  • P9744 消除序列 题解
    本题有多种解法,我这里先讲一个我的考场做法吧。切入点我们发现我们至多使用一次操作一,而剩下部分的\(0\)肯定是依靠操作二补全,操作三的作用只是用来填补操作一的空白的,所以我们发现我们对一个序列的操作一定是前一段用操作一和操作三,后一段用操作二。思路1一开始考虑暴力\(......
  • CEIT 23练习编程题 题解
    本文部分题目提供c/c++两种解法,顺便可以让你们知道c++在面对某些题时的优势部分题目提供多种解法日期格式化C#include<stdio.h>intmain(){intm,d,y;scanf("%d-%d-%d",&m,&d,&y);printf("%04d-%02d-%02d",y,m,d);return0;}02d的含义:当有效数......
  • 【题解】「KDOI-06-S」补题
    「KDOI-06-S」A.「KDOI-06-S」消除序列赛时写了一个\(O(nq)\)的线性DP,喜提60分。注意到如果操作1被使用,则一定只会使用一次,而且在最优策略中一定是第一次使用操作1。则我们可以通过以下方式进行操作,使序列满足条件:首先执行\(a_i\)和\(\sum^{j\lei,i\inP}_{j=......
  • [COCI2015-2016#4] ENDOR 题解
    [COCI2015-2016#4]ENDOR题解首先要发现一个很重要的性质,那就是两只变色龙碰撞后回头,等效于两只变色龙继续往前走,其中向右走的颜色不变,而向左走的要改变颜色。那这样就有一种\(O(n^2)\)的做法:对于向右的变色龙,直接贡献答案;对于向左的变色龙,我们按照碰到的先后顺序枚举它前面......
  • 【题解】AtCoder-ARC167
    AtCoder-ARC167AToastsforBreakfastParty一定不会有空盘,问题转化成\(2m\)个数,其中\(2m-n\)个是\(0\),这样一定是最大值和最小值一起,次大值和次小值一起,以此类推。提交记录:Submission-AtCoderAtCoder-ARC167BProductofDivisors\(A^B=\prod_ip_i^{Bc_i}\),那么答案......