Solution

Method 1 – DFS and Path Counting by Subtree

Intuition

For each server c, the connectable pairs (a, b) must be in different subtrees of c, and the path from c to a and c to b must each have length divisible by signalSpeed. We can use DFS to count, for each subtree, the number of nodes at each distance mod signalSpeed, and then count valid pairs by combining counts from different subtrees.

Approach

Build the tree as an adjacency list.
For each node c (as the center), for each child subtree, use DFS to count the number of nodes at each distance mod signalSpeed.
For each pair of subtrees, count the number of pairs (a, b) such that both distances are divisible by signalSpeed (i.e., both are 0 mod signalSpeed).
For each c, sum the valid pairs from all pairs of subtrees.
Return the answer for all c.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<int> countPairsOfConnectableServers(int n, vector<vector<int>>& edges, int signalSpeed) {\n        vector<vector<pair<int,int>>> g(n);\n        for (auto& e : edges) {\n            g[e[0]].emplace_back(e[1], e[2]);\n            g[e[1]].emplace_back(e[0], e[2]);\n        }\n        vector<int> ans(n);\n        vector<int> cnt;\n        function<void(int,int,int)> dfs = [&](int u, int p, int d) {\n            if (d % signalSpeed == 0) cnt[0]++;\n            for (auto& [v, w] : g[u]) if (v != p) dfs(v, u, d + w);\n        };\n        for (int c = 0; c < n; ++c) {\n            vector<int> subtree_counts;\n            for (auto& [v, w] : g[c]) {\n                cnt = vector<int>(1, 0);\n                dfs(v, c, w);\n                subtree_counts.push_back(cnt[0]);\n            }\n            int total = 0;\n            for (int i = 0; i < subtree_counts.size(); ++i) {\n                for (int j = i+1; j < subtree_counts.size(); ++j) {\n                    total += subtree_counts[i] * subtree_counts[j];\n                }\n            }\n            ans[c] = total;\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"co

Related Tags