题目：100226. 在带权树网络中统计可连接服务器对数目

题目描述

你被给定一个未定根的加权树，它有 n 个顶点，代表从 0 到 n - 1 编号的服务器，一个数组 edges，其中 edges[i] = [ai, bi, weighti] 代表顶点 ai 和 bi 之间的双向边，边的权重为 weighti。你还被给定一个整数 signalSpeed。

如果满足以下条件，两个服务器 a 和 b 可以通过服务器 c 连接：

  • a < b，a != c 且 b != c。
  • 从 c 到 a 的距离可被 signalSpeed 整除。
  • 从 c 到 b 的距离可被 signalSpeed 整除。
  • 从 c 到 b 和从 c 到 a 的路径不共享任何边。

返回一个整数数组 count，长度为 n，其中 count[i] 是通过服务器 i 可连接的服务器对数。

示例

示例 1:

输入: edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1
输出: [0,4,6,6,4,0]
解释: 由于 signalSpeed 为 1，count[c] 等于从 c 出发且不共享任何边的路径对数。
在给定的路径图中，count[c] 等于 c 左侧的服务器数乘以 c 右侧的服务器数。

示例 2:

输入: edges = [[0,6,3],[6,5,3],[0,3,1],[3,2,7],[3,1,6],[3,4,2]], signalSpeed = 3
输出: [2,0,0,0,0,0,2]
解释: 通过服务器 0，有 2 对可连接服务器：(4, 5) 和 (4, 6)。
通过服务器 6，有 2 对可连接服务器：(4, 5) 和 (0, 5)。
可以证明，除了 0 和 6 之外的服务器无法连接任何两个服务器。

限制条件

  • 2 <= n <= 1000
  • edges.length == n - 1
  • edges[i].length == 3
  • 0 <= ai, bi < n
  • 1 <= weighti <= 10^6
  • 1 <= signalSpeed <= 10^6
  • 输入保证 edges 表示一个有效的树。

问题概述

给定一个表示服务器网络的树结构。每个服务器通过带权重的边与其他服务器连接。目标是计算在树中的每个服务器通过的可连接服务器对的数量，这些条件由signalSpeed定义。

可连接服务器的条件

如果满足以下条件，两个服务器 a 和 b 可以通过服务器 c 连接：

  • a < b
  • a 和 b 都不同于 c。
  • 从 c 到 a 和从 c 到 b 的距离都能被 signalSpeed 整除。
  • 从 c 到 a 和从 c 到 b 的路径不共享任何边。

解决方法

  1. 树表示：树使用邻接表表示，每个服务器连接到其邻居以及连接边的权重。

  2. 深度优先搜索（DFS）：

    • 使用修改后的 DFS 算法从每个服务器开始遍历树。
    • 该算法计算所有其他服务器与当前服务器的距离。
    • DFS 确保在路径中不考虑共享边。

  3. 计算可连接对：

    • 对于每个服务器 c，该算法识别通过移除 c 形成的所有可能的子树。
    • 它计算每个子树中与 c 的距离能被 signalSpeed 整除的服务器数量。
    • 通过服务器 c 的可连接对的总数是通过考虑来自不同子树的对的所有可能组合计算出来的。

Python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from collections import defaultdict

def count_connectable_servers(edges, signal_speed):
    def build_tree(edges):
        tree = defaultdict(list)
        for a, b, weight in edges:
            tree[a].append((b, weight))
            tree[b].append((a, weight))
        return tree

    def dfs_count_nodes(server, parent, distance):
        if distance % signal_speed == 0:
            count[0] += 1
        for neighbor, weight in tree[server]:
            if neighbor != parent:
                dfs_count_nodes(neighbor, server, distance + weight)

    n = len(edges) + 1
    tree = build_tree(edges)
    counts = [0] * n

    for c in range(n):
        subtree_counts = []
        for neighbor, weight in tree[c]:
            count = [0]
            dfs_count_nodes(neighbor, c, weight)
            subtree_counts.append(count[0])

        for i in range(len(subtree_counts)):
            for j in range(i + 1, len(subtree_counts)):
                counts[c] += subtree_counts[i] * subtree_counts[j]

    return counts

复杂度分析

  • 时间复杂度：该算法对树中的每个服务器执行一次 DFS。由于每条边在每次 DFS 中被访问一次，并且有 n 个服务器，所以总体时间复杂度为 O(n^2)，其中 n 是服务器的数量。
  • 空间复杂度：由于存储树结构和在 DFS 过程中使用的辅助数据结构，空间复杂度为 O(n)。

测试用例

该解决方案已经通过提供的示例和其他自定义测试用例进行了测试，以确保其正确性。

结论

这个解决方案有效地计算了在树形网络中，每个服务器通过的可连接服务器对的数量，考虑到了与 signalSpeed 和连接规则相关的给定限制。