题解 P4665 【[BalticOI2015] Network】

Leasier · 2022-10-28 00:07:25 · 题解

题意可以转化为：在一棵树上加尽量少的边，使得每条边至少在一个环中。

首先不难通过样例发现下面两个结论：

Observation 1. k = \lceil \frac{leaf}{2} \rceil，其中 leaf 表示叶子数。
Observation 2. 最优方案中的所有 a, b 一定均为叶子。

Observation 2 的证明：

我们显然可以将加一条边 (u, v) 等效为：

让树上 u, v 这条链上的所有边达成“至少在一个环中”的目标。

于是（下文假定我们随意钦定一个点为根且 a 的深度小于 b）：

首先，由于 n \geq 3，原树中不可能仅仅存在 1 个叶子。

于是此时我们将 b 替换为一个 b 子树内的叶子、将 a 替换为一个叶子 a' 使得 lca(a', b) 为 a 的祖先。

此时可以达成目标的最浅点固定为 lca(a, b)。

于是我们把 a, b 分别替换为其子树内的一个叶子即可。

Observation 1 的证明：

首先这玩意显然是答案下界——因为我们会尽量不重复地选叶子。

然后就是人类智慧的一步了——

我们把所有叶子抓出来，按 dfs 序升序排序，前一半与后一半的对应点配对，如果最后单出一个最大的就跟最小的配对。

那它为什么是对的？我们考虑一个非根节点 u。

u$ 子树内叶子个数 $\leq \lfloor \frac{leaf}{2} \rfloor

此时 u \to fa_u 一定会达成目标，因为一定有从内向外的连边。

u$ 子树内叶子个数 $> \lfloor \frac{leaf}{2} \rfloor

显然此时 u 子树内不会涵盖所有叶子，于是最小 / 最大之一总会向其中连边。

至此 Observation 1 得证。然后这道题就做完了。

代码：

#include <stdio.h>

typedef struct {
    int nxt;
    int end;
} Edge;

int cnt = 0;
int head[500007], deg[500007], rnk[500007], leaf[500007];
Edge edge[1000007];

inline void add_edge(int start, int end){
    cnt++;
    edge[cnt].nxt = head[start];
    head[start] = cnt;
    edge[cnt].end = end;
}

void dfs(int u, int father, int &id){
    rnk[++id] = u;
    for (int i = head[u]; i != 0; i = edge[i].nxt){
        int x = edge[i].end;
        if (x != father) dfs(x, u, id);
    }
}

int main(){
    int n, id = 0, leaf_cnt = 0, half;
    scanf("%d", &n);
    for (int i = 1; i < n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        deg[a]++;
        deg[b]++;
        add_edge(a, b);
        add_edge(b, a);
    }
    dfs(1, 0, id);
    for (int i = 1; i <= n; i++){
        if (deg[rnk[i]] == 1) leaf[++leaf_cnt] = rnk[i];
    }
    half = leaf_cnt / 2;
    printf("%d\n", (leaf_cnt + 1) / 2);
    for (int i = 1; i <= half; i++){
        printf("%d %d\n", leaf[i], leaf[i + half]);
    }
    if (leaf_cnt % 2 != 0) printf("%d %d", leaf[1], leaf[leaf_cnt]);
    return 0;
}