题解

建成的道路形成一棵树，若把树随意定根，某条边 $(u,v)$ 的两侧分别包含 $sz$ 与 $n-sz$ 个节点，其中 $sz$ 是以子节点为根的子树大小。题目给定的造价为

$$c \times |\#\text{左} - \#\text{右}| = c \times |(n-sz) - sz| = c \times |n - 2sz|. $$

因此只需要一次 DFS/BFS 求出每条边的子树大小即可。伪代码如下：

1. 用邻接表存储整棵树，任选一点为根；
2. DFS 过程中回溯时累加子树节点数；
3. 遍历到边 $(u,v)$ 时，若 $v$ 是 $u$ 的子节点，则贡献为 $c \times |n - 2 \times sz_v|$；
4. 把所有贡献累加后输出即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。