本文涉及知识点
树上倍增 树 图论 并集查找 换根法 深度优先
割点原理及封装好的割点类(预计2024年3月11号左右发布）
LeetCode3067. 在带权树网络中统计可连接服务器对数目
给你一棵无根带权树，树中总共有 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 构成一棵合法的树。
树上倍增
本题有三个考点：
一，如何计算树上两个节点x1,x2的距离。
假定这两个节点的最早公共祖先是pub。以任意节点root为根，f(x)表示节点x到root的距离。
x1到x2的距离：f(x1)+f(x2)-2*f(pub)。
二，如何找到最早公共祖先：树上倍增。
记录各节点的1级祖先（父节点）、2级祖先、4级祖先…
三，如果判断ac和bc有公共边。
树是连通无向无环图，因为无环，所以两个节点的路径唯一。
假设公共边是x3x4。则x3到c的路径唯一，假定x3到c的倒数第二个端点是x5，则ab和bc的最后一条边都是x 3 c → \overrightarrow{x3c}x3c。断开所以和c相连的边，如果a和b在同一个连通区域，则有公共边。用并查集看是否在同一个连通区域。
时间复杂度： O(nnlogn)。 枚举c，时间复杂度O(n)；枚举ab，时间复杂度O(n)。查公共路径O(logn)。
并集查找
class CNeiBo { public: static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<int>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase); } } return vNeiBo; } static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<std::pair<int, int>>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]); } } return vNeiBo; } }; class CUnionFind { public: CUnionFind(int iSize) :m_vNodeToRegion(iSize) { for (int i = 0; i < iSize; i++) { m_vNodeToRegion[i] = i; } m_iConnetRegionCount = iSize; } CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size()) { for (int i = 0; i < vNeiBo.size(); i++) { for (const auto& n : vNeiBo[i]) { Union(i, n); } } } int GetConnectRegionIndex(int iNode) { int& iConnectNO = m_vNodeToRegion[iNode]; if (iNode == iConnectNO) { return iNode; } return iConnectNO = GetConnectRegionIndex(iConnectNO); } void Union(int iNode1, int iNode2) { const int iConnectNO1 = GetConnectRegionIndex(iNode1); const int iConnectNO2 = GetConnectRegionIndex(iNode2); if (iConnectNO1 == iConnectNO2) { return; } m_iConnetRegionCount--; if (iConnectNO1 > iConnectNO2) { UnionConnect(iConnectNO1, iConnectNO2); } else { UnionConnect(iConnectNO2, iConnectNO1); } } bool IsConnect(int iNode1, int iNode2) { return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2); } int GetConnetRegionCount()const { return m_iConnetRegionCount; } vector<int> GetNodeCountOfRegion()//各联通区域的节点数量 { const int iNodeSize = m_vNodeToRegion.size(); vector<int> vRet(iNodeSize); for (int i = 0; i < iNodeSize; i++) { vRet[GetConnectRegionIndex(i)]++; } return vRet; } std::unordered_map<int, vector<int>> GetNodeOfRegion() { std::unordered_map<int, vector<int>> ret; const int iNodeSize = m_vNodeToRegion.size(); for (int i = 0; i < iNodeSize; i++) { ret[GetConnectRegionIndex(i)].emplace_back(i); } return ret; } private: void UnionConnect(int iFrom, int iTo) { m_vNodeToRegion[iFrom] = iTo; } vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引 int m_iConnetRegionCount; }; class CParents { public: CParents(vector<int>& vParent, const vector<int>& vLeve):m_vLeve(vLeve) { const int iMaxLeve = *std::max_element(vLeve.begin(), vLeve.end()); int iBitNum = 0; for (; (1 << iBitNum) < iMaxLeve; iBitNum++); const int n = vParent.size(); m_vParents.assign(iBitNum+1, vector<int>(n, -1)); m_vParents[0] = vParent; //树上倍增 for (int i = 1; i < m_vParents.size(); i++) { for (int j = 0; j < n; j++) { const int iPre = m_vParents[i - 1][j]; if (-1 != iPre) { m_vParents[i][j] = m_vParents[i - 1][iPre]; } } } } int GetParent(int iNode, int iLeve)const { int iParent = iNode; for (int iBit = 0; iBit < m_vParents.size(); iBit++) { if (-1 == iParent) { return iParent; } if (iLeve & (1 << iBit)) { iParent = m_vParents[iBit][iParent]; } } return iParent; } int GetPublicParent(int iNode1, int iNode2)const { int leve0 = m_vLeve[iNode1]; int leve1 = m_vLeve[iNode2]; if (leve0 < leve1) { iNode2 = GetParent(iNode2, leve1 - leve0); leve1 = leve0; } else { iNode1 = GetParent(iNode1, leve0 - leve1); leve0 = leve1; } //二分查找 int left = -1, r = leve0; while (r - left > 1) { const auto mid = left + (r - left) / 2; const int iParent0 = GetParent(iNode1, mid); const int iParent1 = GetParent(iNode2, mid); if (iParent0 == iParent1) { r = mid; } else { left = mid; } } return GetParent(iNode1, r); } protected: vector<vector<int>> m_vParents; const vector<int> m_vLeve; }; class Solution { public: vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) { m_c = edges.size() + 1; m_vDisToRoot.resize(m_c); m_vParent.resize(m_c); m_vLeve.resize(m_c); auto neiBo = CNeiBo::Three(m_c, edges, false, 0); DFS(neiBo, 0, -1, 0,0); CParents par(m_vParent,m_vLeve); vector<int> vRet(m_c); for (int c = 0; c < m_c; c++) { CUnionFind uf(m_c); for (const auto& v : edges) { if ((v[0] == c) || (v[1] == c)) { continue; } uf.Union(v[0], v[1]); } vector<int> vRegionCnt(m_c); for (int ab = 0; ab < m_c; ab++) { if (ab == c ) { continue; } const int pub = par.GetPublicParent(ab, c); const int len = m_vDisToRoot[ab] + m_vDisToRoot[c] - 2 * m_vDisToRoot[pub]; if (0 != len % signalSpeed) { continue; } vRegionCnt[uf.GetConnectRegionIndex(ab)]++; } int&iRet = vRet[c]; const int total = std::accumulate(vRegionCnt.begin(), vRegionCnt.end(), 0); for (int c1 = 0; c1 < m_c; c1++) { iRet += vRegionCnt[c1] * (total - vRegionCnt[c1]); } iRet /= 2; } return vRet; } void DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par,int leve,int dis) { m_vDisToRoot[cur] =dis; m_vParent[cur] = par; m_vLeve[cur] = leve; for (const auto& [next,len] : neiBo[cur]) { if (next == par) { continue; } DFS(neiBo, next, cur,leve+1,dis+len); } } vector<int> m_vDisToRoot,m_vParent,m_vLeve; int m_c; };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<vector<int>> edges; int signalSpeed; { Solution sln; edges = { }, signalSpeed = 1; auto res = sln.countPairsOfConnectableServers(edges, signalSpeed); Assert({ 0 }, res); } { Solution sln; edges = { {0,1,1} }, signalSpeed = 1; auto res = sln.countPairsOfConnectableServers(edges, signalSpeed); Assert({ 0,0 }, res); } { Solution sln; edges = { {0,1,1},{1,2,1} }, signalSpeed = 1; auto res = sln.countPairsOfConnectableServers(edges, signalSpeed); Assert({ 0,1,0 }, res); } { Solution sln; edges = { {0,1,1},{1,2,5},{2,3,13},{3,4,9},{4,5,2} }, signalSpeed = 1; auto res = sln.countPairsOfConnectableServers(edges, signalSpeed); Assert({ 0,4,6,6,4,0 } , res); } { Solution sln; edges = { {0,6,3},{6,5,3},{0,3,1},{3,2,7},{3,1,6},{3,4,2} }, signalSpeed = 3; auto res = sln.countPairsOfConnectableServers(edges, signalSpeed); Assert({ 2,0,0,0,0,0,2 }, res); } }
【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目（二）https://developer.aliyun.com/article/1478724
