【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目

作者推荐

视频算法专题

本文涉及知识点

树上倍增 树 图论 并集查找 换根法 深度优先
割点原理及封装好的割点类(预计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 <= 10⁶
1 <= signalSpeed <= 10⁶
输入保证 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的最后一条边都是$\overrightarrow{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); 	} } 

换根法DFS

树中删除一个节点，则各孩子各一个连通区域，除自己及后代外一个区域。如果这个节点是根，则简单得多。各孩子一个连通区域。
DSF(cur) 返回自己及子孙到当前根节点距离是signalSpeed 倍的节点数量。令当前根节点各孩子的返回值是{i1,i2,$\cdots$,im} 。i1*i2+(i1+i2)*i3 $\cdots$ +(I1+i2+$\dots$ + i${}_{m-1}$)*im。这样不必除以二。
a<b ，表示a !=b ，(a,b)和(b,a)只取一个。

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 Solution { public: 	vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) { 		m_c = edges.size() + 1; 		m_iSignalSpeed = signalSpeed;		 		auto neiBo = CNeiBo::Three(m_c, edges, false, 0);		 		vector<int> vRet(m_c); 		for (int c = 0; c < m_c; c++) 		{ 			int& iRet = vRet[c]; 			int left = 0; 			for (const auto& [next, len] : neiBo[c]) 			{ 				int cur = DFS(neiBo, next, c, len); 				iRet += left * cur; 				left += cur; 			} 		} 		return vRet; 	} 	int DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par,int dis) 	{ 		int iRet = (0 ==dis % m_iSignalSpeed); 		for (const auto& [next,len] : neiBo[cur]) 		{ 			if (next == par) 			{ 				continue; 			} 			iRet +=DFS(neiBo, next, cur,dis+len); 		} 		return iRet; 	} 	int m_iSignalSpeed; 	int m_c; }; 

割点

本解法过于复杂，除非用了提前封装好的割点扩展类，否则被使用。

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 int iMaxLeve) 	{	 		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; 	}	 protected: 	vector<vector<int>> m_vParents; };  class C2Parents : CParents { public: 	C2Parents(vector<int>& vParent, const vector<int>& vLeve) :m_vLeve(vLeve) 		, CParents(vParent,*std::max_element(vLeve.begin(), vLeve.end())) 	{		 	}	 	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 CCutPointEx { public: 	CCutPointEx(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size()) 	{ 		m_vNodeToTime.assign(m_iSize, -1); 		m_vChildFirstEnd.resize(m_iSize); 		m_vNodeToRegion.assign(m_iSize, -1); 		m_vCut.assign(m_iSize, false); 		for (int i = 0; i < m_iSize; i++) 		{ 			if (-1 != m_vNodeToTime[i]) 			{ 				continue; 			} 			dfs(i, -1, vNeiB); 			m_iRegionCount++; 		} 		m_vTimeToNode.resize(m_iSize); 		for (int i = 0; i < m_iSize; i++) 		{ 			m_vTimeToNode[m_vNodeToTime[i]] = i;; 		} 	} 	bool Visit(int src, int dest, int iCut)const 	{ 		if (m_vNodeToRegion[src] != m_vNodeToRegion[dest]) 		{ 			return false;//不在一个连通区域 		} 		if (!m_vCut[iCut]) 		{ 			return true; 		} 		const int r1 = GetCutRegion(iCut, src); 		const int r2 = GetCutRegion(iCut, dest); 		return r1 == r2; 	} 	vector<vector<int>> GetSubRegionOfCut(const int iCut)const 	{//删除iCut及和它相连的边后，iCut所在的区域会分成几个区域：父节点一个区域、各子节点一个区域 	 //父节点所在区域可能为空，如果iCut所在的连通区域只有一个节点，则返回一个没有节点的区域。 		const auto& v = m_vChildFirstEnd[iCut]; 		vector<vector<int>> vRet(1);			 		int j = 0; 		for (int iTime=0;iTime < m_iSize; iTime++ ) 		{ 			const int iNode	= m_vTimeToNode[iTime]; 			if ((j < v.size()) && ( iTime  >= v[j].first )) 			{ 				j++; 				vRet.emplace_back(); 			} 			if ((iCut != iNode) && (m_vNodeToRegion[iNode] == m_vNodeToRegion[iCut])) 			{ 				if (v.size()&&(iTime >= v.back().second)) 				{ 					vRet[0].emplace_back(iNode); 				} 				else 				{ 					vRet.back().emplace_back(iNode); 				} 			} 		} 		return vRet; 	} protected: 	int dfs(int cur, int parent, const vector<vector<int>>& vNeiB) 	{ 		auto& curTime = m_vNodeToTime[cur]; 		m_vNodeToRegion[cur] = m_iRegionCount; 		curTime = m_iTime++; 		int iCutChild = 0; 		int iMinTime = curTime; 		for (const auto& next : vNeiB[cur]) 		{ 			if (-1 != m_vNodeToTime[next]) 			{ 				iMinTime = min(iMinTime, m_vNodeToTime[next]); 				continue; 			} 			int iChildBeginTime = m_iTime; 			const int iChildMinTime = dfs(next, cur, vNeiB); 			iMinTime = min(iMinTime, iChildMinTime); 			if (iChildMinTime >= curTime) 			{ 				iCutChild++; 				m_vChildFirstEnd[cur].push_back({ iChildBeginTime,m_iTime }); 			}; 		} 		m_vCut[cur] = (iCutChild + (-1 != parent)) >= 2; 		return iMinTime; 	} 	int GetCutRegion(int iCut, int iNode)const 	{ 		const auto& v = m_vChildFirstEnd[iCut]; 		auto it = std::upper_bound(v.begin(), v.end(), m_vNodeToTime[iNode], [](int time, const std::pair<int, int>& pr) {return time < pr.first; }); 		if (v.begin() == it) 		{ 			return v.size(); 		} 		--it; 		return (it->second > m_vNodeToTime[iNode]) ? (it - v.begin()) : v.size(); 	} 	int m_iTime = 0; 	const int m_iSize;//时间戳 	int m_iRegionCount = 0; 	vector<int> m_vNodeToTime;//各节点到达时间，从0开始。 -1表示未处理 	vector<bool> m_vCut;//是否是割点 	vector<int> m_vNodeToRegion;//各节点所在区域 	vector<vector<pair<int, int>>> m_vChildFirstEnd;//左闭右开空间[0,m_vChildFirstEnd[0].first)和[m_vChildFirstEnd.back().second,iSize)是一个区域 	vector<int> m_vTimeToNode; }; 

2024年3月9号 新封装

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 int iMaxLeve) 	{	 		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; 	}	 protected: 	vector<vector<int>> m_vParents; };  class C2Parents : CParents { public: 	C2Parents(vector<int>& vParent, const vector<int>& vLeve) :m_vLeve(vLeve) 		, CParents(vParent,*std::max_element(vLeve.begin(), vLeve.end())) 	{		 	}	 	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 CCutPoint { public: 	CCutPoint(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size()) 	{ 		m_vNodeToTime.assign(m_iSize, -1); 		m_vCutNewRegion.resize(m_iSize); 		for (int i = 0; i < m_iSize; i++) 		{ 			if (-1 == m_vNodeToTime[i]) 			{ 				m_vRegionFirstTime.emplace_back(m_iTime); 				dfs(vNeiB, i, -1); 			} 		}	 	} 	int dfs(const vector<vector<int>>& vNeiB,const int cur, const int parent) 	{ 		int iMinTime = m_vNodeToTime[cur] = m_iTime++; 		int iRegionCount = (-1 != parent);//根连通区域数量 		for (const auto& next : vNeiB[cur])		{ 			if (-1  != m_vNodeToTime[next])			{ 				iMinTime = min(iMinTime, m_vNodeToTime[next]); 				continue; 			} 			const int childMinTime = dfs(vNeiB, next, cur); 			iMinTime = min(iMinTime, childMinTime); 			if (childMinTime >= m_vNodeToTime[cur])			{ 				iRegionCount++; 				m_vCutNewRegion[cur].emplace_back(m_vNodeToTime[next], m_iTime); 			} 		} 		if (iRegionCount < 2) 		{ 			m_vCutNewRegion[cur].clear(); 		} 		return iMinTime; 	} 	const int m_iSize; 	const vector<int>& Time()const { return m_vNodeToTime; }//各节点的时间戳 	const vector<int>& RegionFirstTime()const { return m_vRegionFirstTime; }//各连通区域的最小时间戳 	vector<bool> Cut()const {  		vector<bool> ret; 		for (int i = 0; i < m_iSize; i++) 		{ 			ret.emplace_back(m_vCutNewRegion[i].size()); 		} 		return ret; }// 	const vector < vector<pair<int, int>>>& NewRegion()const { return m_vCutNewRegion; }; protected: 	vector<int> m_vNodeToTime; 	vector<int> m_vRegionFirstTime; 	vector < vector<pair<int, int>>> m_vCutNewRegion; //m_vCutNewRegion[c]如果存在[left,r) 表示割掉c后，时间戳[left,r)的节点会形成新区域 	int m_iTime = 0; };  class CConnectAfterCutPoint  { public: 	CConnectAfterCutPoint(const vector<vector<int>>& vNeiB) :m_ct(vNeiB) 	{ 		m_vTimeToNode.resize(m_ct.m_iSize); 		m_vNodeToRegion.resize(m_ct.m_iSize); 		for (int iNode = 0; iNode < m_ct.m_iSize; iNode++) 		{ 			m_vTimeToNode[m_ct.Time()[iNode]] = iNode; 		} 		for (int iTime = 0,iRegion= 0; iTime < m_ct.m_iSize; iTime++) 		{ 			if ((iRegion < m_ct.RegionFirstTime().size()) && (m_ct.RegionFirstTime()[iRegion] == iTime)) 			{ 				iRegion++; 			} 			m_vNodeToRegion[m_vTimeToNode[iTime]] = (iRegion - 1); 		} 	} 	bool Connect(int src, int dest, int iCut)const 	{ 		if (m_vNodeToRegion[src] != m_vNodeToRegion[dest]) 		{ 			return false;//不在一个连通区域 		} 		if (0 == m_ct.NewRegion()[iCut].size()) 		{//不是割点 			return true; 		} 		const int r1 = GetCutRegion(iCut, src); 		const int r2 = GetCutRegion(iCut, dest); 		return r1 == r2; 	} 	vector<vector<int>> GetSubRegionOfCut(const int iCut)const 	{//删除iCut及和它相连的边后，iCut所在的区域会分成几个区域：父节点一个区域、各子节点		一个区域 			//父节点所在区域可能为空，如果iCut所在的连通区域只有一个节点，则返回一个没有节点的			区域。 		const auto& v = m_ct.NewRegion()[iCut]; 		vector<int> vParen; 		const int iRegion = m_vNodeToRegion[iCut]; 		const int iEndTime = (iRegion + 1 == m_ct.RegionFirstTime().size()) ? m_ct.m_iSize : m_ct.RegionFirstTime()[iRegion+1]; 		vector<vector<int>> vRet;	 		for (int iTime = m_ct.RegionFirstTime()[iRegion],j=-1; iTime < iEndTime; iTime++) 		{ 			if (iCut == m_vTimeToNode[iTime]) 			{ 				continue; 			} 			if ((j + 1 < v.size()) && (v[j + 1].first == iTime)) 			{ 				j++; 				vRet.emplace_back(); 			} 			const int iNode = m_vTimeToNode[iTime]; 			if ((-1 != j ) && (iTime >= v[j].first) && (iTime < v[j].second)) 			{ 				vRet.back().emplace_back(iNode); 			} 			else 			{ 				vParen.emplace_back(iNode); 			}			 		} 		vRet.emplace_back(); 		vRet.back().swap(vParen); 		return vRet; 	}	 protected: 	int GetCutRegion(int iCut, int iNode)const 	{ 		const auto& v = m_ct.NewRegion()[iCut]; 		auto it = std::upper_bound(v.begin(), v.end(), m_ct.Time()[iNode], [](int time, const std::pair<int, int>& pr) {return  time < pr.first; }); 		if (v.begin() == it) 		{ 			return v.size(); 		} 		--it; 		return (it->second > m_ct.Time()[iNode]) ? (it - v.begin()) : v.size(); 	} 	vector<int> m_vTimeToNode; 	vector<int> m_vNodeToRegion;//各节点所在区域 	const CCutPoint m_ct; };  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); 		C2Parents par(m_vParent, m_vLeve); 		auto neiBo2 = CNeiBo::Two(m_c, edges, false, 0); 		CConnectAfterCutPoint cut(neiBo2); 		vector<int> vRet(m_c); 		for (int c = 0; c < m_c; c++) 		{ 			auto regs = cut.GetSubRegionOfCut(c); 			int left = 0; 			int& iRet = vRet[c]; 			for (const auto& subRegion : regs) 			{ 				int cur = 0; 				for (const auto& ab : subRegion) 				{ 					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; 					} 					cur++; 				} 				iRet += left * cur; 				left += cur; 			} 		} 		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; }; 

DFS代替树上倍增

时间复杂度的瓶颈在 树上倍增。可以直接DFS 最近公共祖先。

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 **C+

+17**
如无特殊说明，本算法用**C++**实现。