加权树中可连接服务器计数：枚举根节点 + DFS 子树贡献合并（codeforces-go 双周赛 125 C 题精讲）

• 科学计算

【免费下载链接】codeforces-go

算法竞赛模板库 by 灵茶山艾府 💭💡🎈

项目地址：
https://gitcode.com/GitHub_Trending/co/codeforces-go

点击查看 免费下载

本文基于 codeforces-go 仓库中 LeetCode 双周赛第 125 场 C 题题解展开，完整讲解「统计加权树中可连接服务器对数」的 DFS 枚举解法、叶子剪枝与模运算下沉两种优化，并给出 Python / Java / C++ / Go 四种语言实现及复杂度分析。读完本文，你将掌握一类「以每个节点为根、合并子树贡献计数」的树形枚举套路，并能在 O(n²) 时间、O(n) 空间内独立实现该题，同时了解仓库内配套的测试驱动流程。

题目回顾：什么是「可连接服务器」

题目给出一棵无向加权树，共有 $n$ 个节点（$n$ 等于 edges 数组长度加一），每条边带有权值 wt，并给定整数 signalSpeed。定义：

• 服务器 c 与节点 a 之间距离为路径上边权之和；
• 若该距离能被 signalSpeed 整除（distance % signalSpeed == 0），则称服务器 c 与 a 可连接；
• 对每个服务器 c，要求统计「可连接服务器对」(a, b) 的数量，其中 a ≠ b，且 a、b 均与 c 可连接，但 a 与 b 之间不可直接连接，且路径必须经过 c。

由于题目给定的是树结构，"路径经过 c" 等价于 a、b 必须位于以 c 为根时不同的子树分支中。这是全题最关键的结构性质，也是下文算法的出发点。

核心算法：枚举每个服务器作为根，合并子树贡献

原文档给出一个非常直观的做法：枚举服务器 $c$ 作为树的根，对 $c$ 的每个邻接子树分别做一次 DFS，统计该子树内有多少个节点到 $c$ 的距离是 signalSpeed 的倍数，得到 cnt；再把这些 cnt 两两不同分支地累乘进答案。

具体地，维护一个前缀累计变量 s，对 c 的每一个邻居依次 DFS 得到 cnt，那么：

ans[c] += cnt * s
s += cnt

其中 cnt * s 的含义是：当前分支中的可连接节点与此前所有分支中的可连接节点两两配对，且每对节点必然分属两个不同分支、路径必然经过根 c，从而保证每对 (a, b) 互不可直接连接且满足题意。s 累加后进入下一个分支，即可保证任意两分支间的配对恰好只被统计一次。

这一思路的核心在于 DFS 的返回值定义：

def dfs(x, fa, s):
# 从根 c 走到节点 x 的距离为 s
# 若 s 能被 signalSpeed 整除，说明节点 x 与根 c 可连接，贡献 1
cnt = 0 if s % signalSpeed else 1
for y, wt in g[x]:
if y != fa: # 沿着树向下走，不回父节点
cnt += dfs(y, x, s + wt)
return cnt

fa（父节点）参数用于在无向树上防止回溯，保证 DFS 只在当前分支内部计数，不会跨分支泄漏到其他子树。

优化一：叶子节点直接返回 0（剪枝）

原文档明确指出一个重要优化：

如果 $c$ 只有一个邻居，则答案为 $0$，不调用 dfs。

原因很直观：若根 $c$ 是树的叶子（度数为 1），它只有一个分支。可连接服务器对必须分属两个不同分支，而此时不存在第二个分支，故 ans[c] = 0 是确定的，无需运行 DFS。

原文档还补充了论文 [On the number of leaves in a random recursive tree] 的背景：在随机递归树数据下，叶子节点约占一半，因此这一剪枝在随机数据下可以减少一半的计算量。这一点在四种语言实现中均有体现，统一写成：

for i, gi in enumerate(g):
if len(gi) == 1:
continue # 叶子节点，答案必为 0

优化二：模运算下沉（Python 写法二）

第一种写法在每个节点处用 s % signalSpeed 判断可连接性；第二种写法把取模运算下沉到 DFS 转移过程中：dfs(y, x, (s + wt) % signalSpeed)，这样所有路径距离在遍历中始终保持为 $[0, signalSpeed)$ 的余数，判断条件简化为 s == 0，且天然避免了路径距离溢出与取模运算重复计算。

同时该写法借助 @cache 对 (x, fa, s) 元组做记忆化，由于 s 已被压缩为模数空间内的余数，状态规模可控，递归过程具备复用价值。注意边界细节：第一层递归传入的是 wt % signalSpeed，确保入口处同样落在模数空间内。

@cache
def dfs(x: int, fa: int, s: int) -> int:
cnt = 0 if s else 1
for y, wt in g[x]:
if y != fa:
cnt += dfs(y, x, (s + wt) % signalSpeed)
return cnt

ans = [0] * n
for i, gi in enumerate(g):
if len(gi) == 1:
continue
s = 0
for y, wt in gi:
cnt = dfs(y, i, wt % signalSpeed)
ans[i] += cnt * s
s += cnt

四种语言完整实现

以下是原文档给出的四种语言实现，均已把「叶子剪枝 + 逐分支贡献合并」两个要点落实到代码中。

Python 写法一（不取模、最直白的版本）：

class Solution:
def countPairsOfConnectableServers(self, edges: List[List[int]], signalSpeed: int) -> List[int]:
n = len(edges) + 1
g = [[] for _ in range(n)]
for x, y, wt in edges:
g[x].append((y, wt))
g[y].append((x, wt))

def dfs(x: int, fa: int, s: int) -> int:
cnt = 0 if s % signalSpeed else 1
for y, wt in g[x]:
if y != fa:
cnt += dfs(y, x, s + wt)
return cnt

ans = [0] * n
for i, gi in enumerate(g):
if len(gi) == 1:
continue
s = 0
for y, wt in gi:
cnt = dfs(y, i, wt)
ans[i] += cnt * s
s += cnt
return ans

Java 实现（显式构建邻接表，dfs 以成员方法递归）：

class Solution {
public int[] countPairsOfConnectableServers(int[][] edges, int signalSpeed) {
int n = edges.length + 1;
List<int[]>[] g = new ArrayList[n];
Arrays.setAll(g, i -> new ArrayList<>());
for (int[] e : edges) {
int x = e[0];
int y = e[1];
int wt = e[2];
g[x].add(new int[]{y, wt});
g[y].add(new int[]{x, wt});
}

int[] ans = new int[n];
for (int i = 0; i < n; i++) {
if (g[i].size() == 1) {
continue;
}
int sum = 0;
for (int[] e : g[i]) {
int cnt = dfs(e[0], i, e[1], g, signalSpeed);
ans[i] += cnt * sum;
sum += cnt;
}
}
return ans;
}

private int dfs(int x, int fa, int sum, List<int[]>[] g, int signalSpeed) {
int cnt = sum % signalSpeed == 0 ? 1 : 0;
for (int[] e : g[x]) {
int y = e[0];
if (y != fa) {
cnt += dfs(y, x, sum + e[1], g, signalSpeed);
}
}
return cnt;
}
}

C++ 实现（利用 C++23 递归 lambda 的 this auto&& 自身引用，边以 pair<int,int> 存储）：

class Solution {
public:
vector<int> countPairsOfConnectableServers(vector<vector<int>> &edges, int signalSpeed) {
int n = edges.size() + 1;
vector<vector<pair<int, int>>> g(n);
for (auto &e : edges) {
int x = e[0], y = e[1], wt = e[2];
g[x].push_back({y, wt});
g[y].push_back({x, wt});
}

auto dfs = & -> int {
int cnt = sum % signalSpeed == 0;
for (auto &[y, wt] : g[x]) {
if (y != fa) {
cnt += dfs(y, x, sum + wt);
}
}
return cnt;
};

vector<int> ans(n);
for (int i = 0; i < n; i++) {
if (g[i].size() == 1) {
continue;
}
int sum = 0;
for (auto &[y, wt] : g[i]) {
int cnt = dfs(y, i, wt);
ans[i] += cnt * sum;
sum += cnt;
}
}
return ans;
}
};

Go 实现（即仓库源码 c.go 的完整版本，递归用闭包 + 外部变量 cnt 累计）：

func countPairsOfConnectableServers(edges [][]int, signalSpeed int) []int {
n := len(edges) + 1
type edge struct{ to, wt int }
g := make([][]edge, n)
for _, e := range edges {
x, y, wt := e[0], e[1], e[2]
g[x] = append(g[x], edge{y, wt})
g[y] = append(g[y], edge{x, wt})
}

ans := make([]int, n)
for i, gi := range g {
if len(gi) == 1 {
continue
}
var cnt int
var dfs func(int, int, int)
dfs = func(x, fa, sum int) {
if sum%signalSpeed == 0 {
cnt++
}
for _, e := range g[x] {
if e.to != fa {
dfs(e.to, x, sum+e.wt)
}
}
}
sum := 0
for _, e := range gi {
cnt = 0
dfs(e.to, i, e.wt)
ans[i] += cnt * sum
sum += cnt
}
}
return ans
}

复杂度分析

• 时间复杂度：$\\mathcal{O}(n^2)$，其中 $n$ 为 edges 的长度加一（即树节点数）。外层枚举每个根 $c$ 至多 $n$ 次，每次对整棵树做一次 DFS；配合叶子剪枝后，实际运行次数在随机数据下可显著减少（约一半的根节点直接跳过）。
• 空间复杂度：$\\mathcal{O}(n)$，用于存储邻接表 g 与答案数组 ans，递归深度在树退化为链时可达 $O(n)$。

仓库实现与测试驱动验证

本题在 codeforces-go 仓库中保留了完整的「源码 + 测试 + 样例数据」三件套，路径位于 leetcode/biweekly/125/c/：

• 实现：c.go 中的 countPairsOfConnectableServers，与上文 Go 版本完全一致；
• 测试：c_test.go 通过 testutil.RunLeetCodeFuncWithFile(t, countPairsOfConnectableServers, "c.txt", 0) 读取样例文件驱动测试；
• 样例数据：c.txt 以「输入（edges 与 signalSpeed 各一行）+ 期望输出（一行）」为一组，目前包含两组用例：

[[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]]
1
[0,4,6,6,4,0]

[[0,6,3],[6,5,3],[0,3,1],[3,2,7],[3,1,6],[3,4,2]]
3
[2,0,0,0,0,0,2]

以第二组为例：节点 3 与节点 0、1、2、4 的距离分别为 1、6、7、2，signalSpeed = 3 时可连接节点为 1（距离 6）与 2（距离 7 取模不整除？7%3=1）——实际可连接的为距离可被 3 整除的节点，最终 ans[3] = 2（0 与 6、5 分支中的 1 和 2 形成两对），其余节点的答案符合输出 [2,0,0,0,0,0,2]。

这套测试基础设施由仓库的模板生成器维护：测试文件头部注释标明 "Generated by copypasta/template/leetcode/generator_test.go"，即 generator_test.go 中的 genLeetCodeTests 通过 GetBiweeklyContestID 自动定位双周赛目录并批量生成题目测试；而 leetcode.go 中的 RunLeetCodeFuncWithFile 负责把文本样例按「每 fNumIn + fNumOut 行一组」切分，并经 parseRawArg 按反射类型解析成函数入参，随后逐个用例断言输出。

延伸思考与相似题目

原文档为该题配套了进阶思考题：

如果 $n = 10^5,\\ \\text{signalSpeed} = 10$，你能想出一个更快的做法吗？

此时 $O(n^2)$ 的枚举根节点方案不再可行。可参考 Codeforces 791D Bear and Tree Jumps（树形 DP 按余数分类计数）的思路，用一次全树 DP 处理距离模 $k$ 的统计问题，将复杂度降到 $O(n \\cdot \\text{signalSpeed})$ 级别——这提示我们：当模数很小而 $n$ 很大时，余数维度可以充当 DP 状态的一部分，与本文第二种写法中「把路径距离压缩到模数空间」的思路一脉相承。

原文档还给出了相似题目：

• LeetCode 2867 统计树中的合法路径数目：同样是树上的路径计数问题，可在此基础上进一步练习「按质数分类 + 并查集/DFS 合并贡献」的套路。

若需系统化训练，仓库的 leetcode/SOLUTIONS.md（由作者维护的题解精选索引）以及原文档附带的分类题单（滑动窗口、二分、图论、动态规划、常用数据结构、数学算法、字符串等 12 大类）可帮助按知识点查漏补缺。结合本仓库 README 描述的项目定位（算法竞赛模板库），此类题解文档与 copypasta 模板、测试基建共同构成了从「看懂题解」到「可复现验证」的完整闭环。

赞

分享

• 科学计算

【免费下载链接】codeforces-go

算法竞赛模板库 by 灵茶山艾府 💭💡🎈

项目地址：
https://gitcode.com/GitHub_Trending/co/codeforces-go

点击查看 免费下载

相关推荐

• codeforces-go中的树结构：树的节点访问

  codeforces go中的树结构：树的节点访问 还在为算法竞赛中的树结构问题头疼吗？codeforces go项目提供了完整的树结构实现方案，助你轻松掌握树

  科学计算

• codeforces-go中的树结构：树的节点类型解析

  codeforces go中的树结构：树的节点类型解析 还在为算法竞赛中的树结构问题头疼吗？一文带你彻底掌握codeforces go项目中各种树结构的节点类型

  科学计算

• 大麦网自动抢票脚本完整指南：运行机制、参数配置与故障排查

  大麦网自动抢票脚本完整指南：运行机制、参数配置与故障排查 热门演出开票即售罄，核心瓶颈是下单请求的速度。Automatic_ticket_purchase 是一

  网页爬虫
  工作流自动化

上一篇：
Voldemort入门指南：5分钟快速搭建分布式键值存储系统

下一篇：
YOLOv5 模型压缩实战：从剪枝、INT8 量化到边缘部署全解析

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考