給你一棵無根帶權樹，樹中總共有?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;
//     }
// };