#CF2272D. Connecting the Conflicts
Connecting the Conflicts
题目描述
树是一个无环的连通图。树的独立集定义为树中一个顶点集合,使得集合中任意两个不同顶点在树中都没有边直接相连。最大独立集是指包含尽可能多顶点的独立集。
给定一个由 $k$ 棵树组成的森林,我们需要添加 $k-1$ 条边将森林合并为一棵树,使得结果树的最大独立集的大小尽可能大。请找出需要添加的边。
如果有多个合法答案,你可以输出其中任意一个。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$($1 \le t \le 10^4$)。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 $k$($2 \le k \le 2 \cdot 10^5$)— 森林中树的数量。
接下来是 $k$ 棵树中每棵树的描述,它们按顺序编号为 $1, 2, \ldots, k$:
第一行包含一个整数 $n$($1 \le n \le 2 \cdot 10^5$)— 树的大小。该树的顶点编号为从 $1$ 到 $n$ 的整数。
接下来的 $n-1$ 行每行包含两个整数 $u$ 和 $v$($1 \le u,v \le n$,$u \ne v$),表示顶点 $u$ 和 $v$ 之间的边。保证给定的边构成一棵树。
保证所有测试用例中 $k$ 的总和不超过 $2 \cdot 10^5$。
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
输出格式
对于每个测试用例,输出 $k-1$ 行;每行包含四个整数 $t_1, v_1, t_2, v_2$,表示在原始图上添加一条连接 $(t_1,v_1)$ 和 $(t_2,v_2)$ 的边。
注意,我们按照 $k$ 棵树在输入数据中出现的顺序将它们从 $1$ 到 $k$ 编号。对于任意一棵树 $i$($1 \le i \le k$),如果它包含 $n$ 个节点,则其节点编号为 $1$ 到 $n$。这棵树中的第 $j$ 个节点记为 $(i,j)$。
样例
2
2
1
1
2
3
1 2
1 3
1
2 1 1 1
2 1 1 1
说明
在第一个测试用例中,图有两个顶点和一条边;在这两个节点之间添加一条边是将图变成树的唯一方法。
在第二个测试用例中,我们可以在树 $2$ 唯一的顶点 $1$ 和树 $1$ 的顶点 $1$、$2$、$3$ 中的一个之间添加边。
- 添加边 $(2,1)-(1,1)$,结果树的最大独立集大小为 $3$。
- 添加边 $(2,1)-(1,2)$,结果树的最大独立集大小为 $2$。
- 添加边 $(2,1)-(1,3)$,结果树的最大独立集大小为 $2$。
因此,我们选择边 $(2,1)-(1,1)$,因为这是最优的。
来源
导入自 Codeforces — Codeforces Round 1130 (Div. 2)。