Loading... > https://leetcode.cn/problems/count-pairs-of-connectable-servers-in-a-weighted-tree-network/description/?envType=daily-question&envId=2024-05-06 必须要通过服务器 $c$ 连接，也就是 $a, b$ 之间的路径必须包含 $c$ 。因为输入是一棵带权树，所以可以将 $c$ 作为顶点来搜索。 $a, b$ 到 $c$ 的路径不能有重复，因此 $a, b$ 必须在 $c$ 的不同子树上，这样就不会出现重复的路径，并且也保证了必定会经过 $c$ 。 $a, b$ 到 $c$ 的距离必须可以被 `signalSpeed` 整除，判断一下即可。 因此只需要对每个顶点做一次 DFS ，找到每棵子树中符合条件的点，然后将其两两相乘求和即可。 ````c++ class Solution { public: std::vector<int> countPairsOfConnectableServers(std::vector<std::vector<int>>& edges, int signalSpeed) { const int n = edges.size() + 1; std::vector<std::vector<std::pair<int, int>>> graph(n); for (auto &edge : edges) { graph[edge[0]].emplace_back(edge[1], edge[2]); graph[edge[1]].emplace_back(edge[0], edge[2]); } std::function<int(int, int, int)> dfs = [&] (int node, int parent, int weight) { int cnt = weight % signalSpeed == 0; for (auto &[nextNode, nextWeight] : graph[node]) { if (nextNode != parent) cnt += dfs(nextNode, node, weight + nextWeight); } return cnt; }; std::vector<int> res(n); for (int i = 0; i < n; i++) { int sum = 0; for (auto &[node, weight] : graph[i]) { int cnt = dfs(node, i, weight); res[i] += sum * cnt; sum += cnt; } } return res; } }; ```` - 时间复杂度：$O(n^2)$ ，其中 $n$ 为 `edge` 的长度加一。 - 空间复杂度：$O(n)$ 。 最后修改：2024 年 06 月 04 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏