题解

原网络是一棵树，要让任意一条原有网线断开后仍保持连通，只需把所有叶子两两连成新的边，让每个叶子拥有不少于两条独立的出路。程序先用 DFS 遍历整棵树，借助 head 链表判断度数等于 1 的节点，将所有叶子按遍历顺序存入数组 lf。设叶子总数为 cnt，所需新边数即 ⌈cnt / 2⌉：把 lf 的前半段与后半段一一配对即可；当叶子数为奇数时，最后一个叶子与第一个叶子再连一条边。这样每个原来的叶子节点都多出一条冗余路径，整张图在删去任一原边后依旧连通。

#include <iostream>
#define MAXN 500003
using namespace std;

struct Edge
{
    int to, nxt;
} edges[MAXN << 1 | 1];
int cnt, head[MAXN], lf[MAXN];

inline void add_edge(const int &from, const int &to)
{
    edges[++cnt] = {to, head[from]}, head[from] = cnt;
}
void dfs(const int &u, const int &fa)
{
    if (!edges[head[u]].nxt)
        lf[++cnt] = u;
    for (int i = head[u], to; i; i = edges[i].nxt)
    {
        to = edges[i].to;
        if (to == fa)
            continue;
        dfs(to, u);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, u, v;
    cin >> n;
    for (int i = 1; i < n; ++i)
        cin >> u >> v, add_edge(u, v), add_edge(v, u);
    cnt = 0, dfs(1, 0);
    cout << ((cnt + 1) >> 1) << '\n';
    for (int i = 1; i <= ((cnt + 1) >> 1); ++i)
        cout << lf[i] << ' ' << lf[i + (cnt >> 1)] << '\n';
    return 0;
}