当前位置：首页 > news >正文

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

news 来源：原创 2024/7/1 5:22:35

给你一棵无根带权树，树中总共有 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 可连接 的服务器对的数目。

示例 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 左边服务器数目乘以右边服务器数目。

示例 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 才可连接，所以其他服务器对应的可连接服务器对数目都为 0 。

提示：

·2 <= n <= 1000

·edges.length == n - 1

·edges[i].length == 3

·0 <= ai, bi < n

·edges[i] = [ai, bi, weighti]

·1 <= weighti <= 106

·1 <= signalSpeed <= 106

·输入保证 edges 构成一棵合法的树。

题目大意：计算每个结点可连接的服务器对数。

分析：

（1）将某个结点看作根，只有该结点有多个子树时，该结点才有可连接的服务器对，否则由于其余服务器到该结点有公共边，该结点可连接的服务器对数为0；

（2）基于（1）中结论，某个结点可连接的服务器对数ans[i]计算方式如下（将与该结点的距离是signalSpeeed倍数的结点称之为符合要求的结点）：用深度优先遍历算法计算每个子树符合要求的结点个数，ans[i]即为这些子树中符合要求的结点进行交叉配对最多可以配对的服务器对数；

（3）根据（2）中算法可以得到1个结点可连接的对数，采取相同做法对每个结点进行深度优先遍历就能计算得到每个结点可连接的服务器对数；

（4）本题结点较多，采用邻接矩阵存储时间复杂度较高，为O(N3)，会超时，但所给数据结构是树，只有n-1条边，考虑到边较少，因此采用邻接表存储，将时间复杂度降为O(N2)。

class Solution {
public:vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {int N=edges.size()+1,sumNode,sum;vector<vector<pair<int,int>>> dis(N);vector<int> ans(N,0);function<int(int,int,int)> dfs=[&](int root,int parent,int length){int num=0;if(!length) ++num;for(auto& [node,len]:dis[root]){if(node!=parent) num+=dfs(node,root,(length+len)%signalSpeed);}return num;};for(auto& ele:edges){dis[ele[0]].emplace_back(ele[1],ele[2]);dis[ele[1]].emplace_back(ele[0],ele[2]);}for(int i=0;i<N;++i){sum=0;for(auto& [root,len]:dis[i]){sumNode=dfs(root,i,len%signalSpeed);ans[i]+=sumNode*sum;sum+=sumNode;}}return ans;}
};
//邻接矩阵存储，超时的算法
// class Solution {
// public:
//     vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
//         int N=edges.size()+1,sumNode,sum;
//         vector<vector<int>> dis(N,vector<int>(N,0));
//         vector<int> ans(N,0);
//         function<int(int,int,int)> dfs=[&](int node,int parent,int length){
//             int num=0;
//             length+=dis[parent][node];
//             if(!(length%signalSpeed)) ++num;
//             for(int i=0;i<dis.size();++i){
//                 if(dis[node][i]>0&&i!=parent) num+=dfs(i,node,length);
//             }
//             return num;
//         };
//         for(int i=0;i<N-1;++i) dis[edges[i][0]][edges[i][1]]=dis[edges[i][1]][edges[i][0]]=edges[i][2];
//         for(int i=0;i<N;++i){
//             sum=0;
//             for(int j=0;j<N;++j){
//                 if(dis[i][j]>0){
//                     sumNode=dfs(j,i,0);
//                     ans[i]+=sumNode*sum;
//                     sum+=sumNode;
//                 }
//             }
//         }
//         return ans;
//     }
// };