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

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

给你一棵无根带权树，树中总共有 n 个节点，分别表示 n 个服务器，服务器从 0 到 n - 1 编号。同时给你一个数组 edges ，其中 edges[i] = [ai, bi, weighti] 表示节点 ai 和 bi 之间有一条双向边，边的权值为 weighti 。再给你一个整数 signalSpeed 。

如果两个服务器 a ，b 和 c 满足以下条件，那么我们称服务器 a 和 b 是通过服务器 c 可连接的 ：

• a < b ，a != c 且 b != c 。
• 从 c 到 a 的距离是可以被 signalSpeed 整除的。
• 从 c 到 b 的距离是可以被 signalSpeed 整除的。
• 从 c 到 b 的路径与从 c 到 a 的路径没有任何公共边。

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

选择 c 作为根节点，不同子树中进行深度搜索，在不同子树的节点，就不会有公共边，不同子树中满足条件的节点数相乘就是所得结果。

如何存储其连接和权值，可以使用List<int[]>[]进行存储，也可以使用二维数组进行存储。

不需要考虑 a 和 b 的大小关系，我们选择一对，总有一个大的值。

还有就是条件并没有说明，它是一棵无根二叉树，它可能是多叉树。因此要计算某一棵子树与其他剩余子树满足条件的节点。

完整代码

class Solution {
    public int[] countPairsOfConnectableServers(int[][] edges, int signalSpeed) {
        int n = edges.length + 1;

        List<int[]>[] graph = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            graph[u].add(new int[]{v, w});
            graph[v].add(new int[]{u, w});
        }

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int p = 0;
            for (int[] num : graph[i]) {
                int cnt = dfs(i, num[0], num[1], signalSpeed, graph);
                res[i] += p * cnt;
                p += cnt;
            }
        }
        return res;
    }

    public int dfs(int pre, int cur, int cost, int signalSpeed, List<int[]>[] graph) {
        int res = 0;
        if (cost % signalSpeed == 0) {
            res++;
        }
        for (int[] num : graph[cur]) {
            if (num[0] == pre) continue;
            res += dfs(cur, num[0], cost + num[1], signalSpeed, graph);
        }
        return res;
    }
}

用二维数组存储的完整代码

class Solution {
    public int[] countPairsOfConnectableServers(int[][] edges, int signalSpeed) {
        int n = edges.length + 1;

        int[][] weight = new int[n][n];
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            weight[u][v] = w;
            weight[v][u] = w;
        }

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int p = 0;
            for (int j = 0; j < n; j++) {
                if (weight[i][j] == 0 || j == i) continue;
                int cnt = dfs(n, i, j, weight[i][j], signalSpeed, weight);
                res[i] += p * cnt;
                p += cnt;
            }
        }
        return res;
    }

    public int dfs(int n, int pre, int cur, int cost, int signalSpeed, int[][] weight) {
        int res = 0;
        if (cost % signalSpeed == 0) {
            res++;
        }
        for (int j = 0; j < n; j++) {
            if (weight[cur][j] == 0 || j == cur || j == pre) continue;
            res += dfs(n, cur, j, cost + weight[cur][j], signalSpeed, weight);
        }
        return res;
    }
}

上述用二维数组存储的方法，浪费了大量空间，一个节点至于少数节点连接而有权值，大部分存储为 0，因此造成空间的浪费。

而且在搜索时，要扫描所有位置，也会造成时间的浪费。