3067. 在帶權樹網絡中統計可連接伺服器對數目#
給你一棵無根帶權樹，樹中總共有 個節點，分別表示 個伺服器，伺服器從 到 編號。同時給你一個陣列 ，其中 表示節點 和 之間有一條雙向邊，邊的權值為 。再給你一個整數 。
如果兩個伺服器 ， 和 滿足以下條件，那麼我們稱伺服器 和 是通過伺服器 可連接的：
- ， 且 。
- 從 到 的距離是可以被 整除的。
- 從 到 的距離是可以被 整除的。
- 從 到 的路徑與從 到 的路徑沒有任何公共邊。
請你返回一個長度為 的整數陣列 ，其中 表示通過伺服器 可連接 的伺服器對的 數目 。
示例 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 。
提示：
- 輸入保證 構成一棵合法的樹。
根枚舉#
- ， 且 。
- 從 到 的距離是可以被 整除的。
- 從 到 的距離是可以被 整除的。
- 從 到 的路徑與從 到 的路徑沒有任何公共邊。
從可連接的條件中我們可以得到以下資訊：
- a 和 b 位置可以互換，只需要滿足存在差值即可。（也可以理解為防止重複）
- c 是將這個無向無環圖分為兩個部分的節點，因為只有這樣 c 到 a 的路徑與 c 到 b 的路徑才沒有任何公共邊。
分析以下案例：
遍歷到子樹 1：
遍歷到子樹 2：
遍歷到子樹 3：
將每一次遍歷的滿足條件的結果相加即為當前遍歷的根節點的可連接節點對。
程式碼實現：
class Solution {
public:
vector<int> countPairsOfConnectableServers(vector<vector<int>> &edges, int signalSpeed) {
int n = edges.size() + 1; // 邊比節點數少 1
// {root, [<child1, cost1>, <child2, cost2>, ..., <childn, costn>]}
vector<vector<pair<int, int>>> graph(n);
for (const auto &edge : edges) {
graph[edge[0]].push_back({edge[1], edge[2]});
graph[edge[1]].push_back({edge[1], edge[2]});
}
/// @brief
/// @param root 根節點，傳入該參數是為了防止子樹根節點走向該節點
/// @param child 子節點
/// @param remainder root 到 child 的根節點的距離
/// @return 返回以 root 根節點，child 為其中一個子樹，子樹有多少個滿足到達路徑可以被 signalSpeed 整除的節點
function<int(int, int, int)> dfs = [&](int root, int child, int remainder) -> int {
int res = 0;
if (remainder == 0) {
++res;
}
// 遍歷子節點的所有子樹
for (const auto &[j, cost] : graph[child]) {
// 排除根節點路徑
if (j != root) {
res += dfs(child, j, (remainder + cost) % signalSpeed);
}
}
return res;
};
vector<int> res(n);
// 遍歷根節點
for (int i = 0; i < n; ++i) {
int pre = 0; // 統計根節點子樹的可連接對數
// 遍歷根節點的所有子樹
for (auto &[j, cost] : graph[i]) {
// 當前子樹滿足的條件的節點個數
int cnt = dfs(i, j, cost % signalSpeed);
res[i] += pre * cnt;
pre += cnt;
}
}
return res;
}
};