• Leetcode 3067. Count Pairs of Connectable Servers in a Weighted Tree Network
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3067. Count Pairs of Connectable Servers in a Weighted Tree Network

1. 解題思路

這一題沒想到什么好的方法，走的是暴力求解的路子。

整體的思路上其實還是比較直接的，就是考察所有的節點作為根節點時的單項路徑，然后篩選出其中所有的和可以被signalSpeed整除的路徑數目，最后求一下兩兩組合的對數即可。

其中，前者可以通過一個深度優先遍歷進行實現；而后者事實上就是如下公式：

$$\begin{array}{rl}s& =\sum _{i<j}{x}_i?x_j\\ & =\frac{1}{2}?\sum _i{x}_i?(\sum _{j\ne i}{x}_j)\\ & =\frac{1}{2}?\sum _i{x}_i?(\sum _j{x}_j?x_i)\end{array}$$

因此，我們通過一重循環就能夠快速地得到對應的答案。

2. 代碼實現

給出python代碼實現如下：

class Solution:def countPairsOfConnectableServers(self, edges: List[List[int]], signalSpeed: int) -> List[int]:n = len(edges)+1graph = defaultdict(list)for u, v, w in edges:graph[u].append((v, w))graph[v].append((u, w))@lru_cache(None)def dfs(u, pre, distance):ans =  1 if distance == 0 else 0for v, w in graph[u]:if v == pre:continueans += dfs(v, u, (distance + w) % signalSpeed)return ansdef count_connectable(u):cnt = [dfs(v, u, w % signalSpeed) for v, w in graph[u]]s = sum(cnt)ans = sum([x * (s-x) for x in cnt]) // 2return ansreturn [count_connectable(u) for u in range(n)] 

提交代碼評測得到：耗時292ms，占用內存38.7MB。