题目大意

给定一个连通无向图 $G$，要求构造一个新图 $G'$，使得对于任意节点 $a$ 和步数 $b$，从节点 $1$ 到 $a$ 是否存在长度为 $b$ 的路径在 $G$ 和 $G'$ 中相同。求 $G'$ 的最小边数。

核心思路

关键观察

1. 距离奇偶性：对于每个节点，记录到它的最短偶距离和最短奇距离
2. 路径存在性：$f_G(a,b)$ 为真当且仅当 $b \ge dis[a][b\bmod 2]$ 且 $b$ 与某个可达距离同奇偶
3. 图简化：只需要保持每个节点的两个最短距离值不变

算法步骤

1. BFS 计算最短距离

void bfs() {
    // 计算每个节点的 dis[i][0] 和 dis[i][1]
    // 分别表示到节点 i 的偶数和奇数最短距离
}

2. 节点分类

• 对于每个节点 $i$，得到距离对 $(d_0, d_1)$，其中 $d_0 \le d_1$
• 按 $c = \lfloor (d_0 + d_1 - 1)/2 \rfloor$ 将节点分组

3. 贪心构造

对于每个 $c$ 值对应的节点组：

• 维护当前可用的连接数 cnt
• 按距离 $d_0$ 从小到大处理节点
• 尽量复用已有的连接，必要时创建新连接

4. 特殊情况处理

• 如果节点 $1$ 没有奇数距离路径，直接输出 $n-1$（生成树）
• 对于边界情况，如 $d_0 = 0$（节点 $1$ 自身）特殊处理

复杂度分析

• 时间复杂度：$O(T \cdot (n + m))$，其中 $T$ 是测试用例数
• 空间复杂度：$O(n + m)$

总结

本题的关键在于理解：保持图的路径存在性等价于保持每个节点的奇偶最短距离。通过巧妙的节点分组和贪心构造，可以在满足条件的前提下最小化边数。