CF1284F New Year and Social Network

Donghyun 的新社交网络服务（SNS）包含 $n$ 个用户，编号为 $1, 2, \ldots, n$。在内部，他们的网络结构是一棵树图，因此有 $n-1$ 条直接连接，每个用户之间都可以通过若干直接连接到达彼此。我们将这个主网络记为 $T_1$。 为了防止服务器故障，Donghyun 创建了一个备份网络 $T_2$，它同样通过一棵树图连接这 $n$ 个用户。如果系统发生故障，$T_1$ 中恰好有一条边 $e$ 变得不可用。此时，Donghyun 会通过选择 $T_2$ 中的另一条边 $f$，并将其加入现有网络，以恢复网络的连通性。 Donghyun 希望为 $T_1$ 中尽可能多的边 $e$ 分配一条替换边 $f \in T_2$。但由于备份网络 $T_2$ 很脆弱，每条 $T_2$ 的边 $f$ 最多只能作为一条 $T_1$ 边的替换边。满足这个限制的前提下，Donghyun 想要保护 $T_1$ 中尽可能多的边。 形式化地，设 $E(T)$ 表示树 $T$ 的边集。我们考虑一个二分图，两侧分别为 $E(T_1)$ 和 $E(T_2)$。对于 $e \in E(T_1), f \in E(T_2)$，当且仅当图 $T_1 - \{e\} + \{f\}$ 仍然是一棵树时，二分图中存在一条连接 $\{e, f\}$ 的边。你需要在这个二分图中找到最大匹配。

第一行包含一个整数 $n$（$2 \le n \le 250\,000$），表示用户数量。 接下来 $n-1$ 行，每行包含两个整数 $a_i, b_i$（$1 \le a_i, b_i \le n$），表示 $T_1$ 中一条边连接的两个顶点。 再接下来 $n-1$ 行，每行包含两个整数 $c_i, d_i$（$1 \le c_i, d_i \le n$），表示 $T_2$ 中一条边连接的两个顶点。 保证两组边集均构成一棵大小为 $n$ 的树。

第一行输出一个整数 $m$（$0 \leq m < n$），表示最多可以保护的边数。 接下来 $m$ 行，每行输出四个整数 $a_i, b_i, c_i, d_i$，表示 $T_1$ 中的边 $(a_i, b_i)$ 可以被 $T_2$ 中的边 $(c_i, d_i)$ 替换。 所有输出的边都应属于各自的网络，并且每条边只能被分配一次。如果从 $T_1$ 中删除 $(a_i, b_i)$ 并加入 $T_2$ 中的 $(c_i, d_i)$，网络应保持连通。输出边的顺序以及每条边的顶点顺序均不影响答案。 如果有多组解，输出任意一组均可。

由 ChatGPT 4.1 翻译