社区讨论

请求修改翻译

GGraphcity
CF237D T-decomposition参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lo7tjqke
此快照首次捕获于
2023/10/27 07:31
2 年前
此快照最后确认于
2023/10/27 07:31
2 年前
查看原帖

题目描述

给定一棵 nn 个结点的无根树 ss，它的点集为 VV。你需要构造出一棵无根树 tt，每个结点 xix_i 是 VV 中的一个非空子集。这棵树需要满足下列要求：
  • 所有 xix_i 的并集为 VV。
  • 对于树 ss 中的任意一条边 (a,b)(a,b)，在 tt 中都能够找到一个集合 xx 使得 a,b∈xa,b\in x。
  • 对于树 ss 中的任意一个点 aa，所有在 tt 中包含了 aa 的集合构成了一个连通块。
设你构造出来的树 tt 的价值为 tt 中最大集合的大小。你的构造需要满足在价值最小的前提下，集合个数最少。1≤n≤1051\le n\le 10^5。

输入格式

第一行，输入 nn。
接下来 n−1n-1 行，每行输入两个数 a,ba,b 表示树 ss 中的一条边。

输出格式

第一行，输出 tt 中的集合个数 kk。
接下来 kk 行，每行表示一个集合。第一个数输出集合的大小 pp，接下来 pp 个数输出这个集合中的元素。
接下来 k−1k-1 行，每行输出两个数 a,ba,b，表示连接树 tt 中的第 aa 个和第 bb 个集合。

回复

共 6 条回复，欢迎继续交流。

正在加载回复...