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

链接：3067.在带权树网络中统计可连接服务器对数目
难度：Medium
标签：树、深度优先搜索、数组
简介：请你返回一个长度为 n 的整数数组 count ，其中 count[i] 表示通过服务器 i 可连接 的服务器对的 数目 。

题解 1 - python

• 编辑时间：2024-06-04
• 执行用时：797ms
• 内存消耗：18.23MB
• 编程语言：python
• 解法介绍：模拟。

class Solution:
    def countPairsOfConnectableServers(self, edges: List[List[int]], signalSpeed: int) -> List[int]:
        nodes = [[] for _ in range(len(edges) + 1)]
        for n1, n2, w in edges:
            nodes[n1].append((n2, w))
            nodes[n2].append((n1, w))
        def dfs(cur: int, prev: int, sum: int) -> int:
            res = 0
            if sum % signalSpeed == 0: res += 1
            for next, w in nodes[cur]:
                if next != prev:
                    res += dfs(next, cur, sum + w)
            return res
        def get_cnt(cur: int) -> int:
            if len(nodes[cur]) == 1: return 0
            arr = [dfs(next, cur, w) for next, w in nodes[cur]]
            vsum = sum(arr)
            res = 0
            for v in arr:
                vsum -= v
                res += v * vsum
            return res
        return [get_cnt(i) for i in range(len(nodes))]