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

作者推荐

视频算法专题

本文涉及知识点

树上倍增 树 图论 并集查找 换根法 深度优先 割点

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);
	}
}

换根法DFS

树中删除一个节点，则各孩子各一个连通区域，除自己及后代外一个区域。如果这个节点是根，则简单得多。各孩子一个连通区域。
DSF(cur) 返回自己及子孙到当前根节点距离是signalSpeed 倍的节点数量。令当前根节点各孩子的返回值是{i1,i2, ⋯ \cdots ⋯,im} 。i1*i2+(i1+i2)*i3 ⋯ \cdots ⋯ +(I1+i2+ … \dots … + i m − 1 _{m-1} 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;
};

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++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/435772.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Wireshark_labs TCP

Wireshark_labs TCP

在本实验中&#xff0c;我们将详细研究著名的TCP协议的行为。我们将通过从您的电脑向远程服务器传输一份150KB 的文件(一份Lewis Carrol 的“爱丽丝梦游仙境”文本)&#xff0c; 并分析TCP传输内容的发送和接收过程来实现。我们将研究TCP对序列和确认号的使用&#xff0c;以提供…
阅读更多...
Proxmox VE安装CentOS

Proxmox VE安装CentOS

1、下载CentOS镜像文件 阿里巴巴开源镜像站&#xff1a; https://developer.aliyun.com/mirror/ CentOS 镜像文件 https://mirrors.aliyun.com/centos/8.5.2111/isos/x86_64/CentOS-8.5.2111-x86_64-dvd1.iso 2、上传ISO镜像 选择ISO镜像上传 3、创建虚拟机 1、点击【创…
阅读更多...
python转换json

python转换json

import json import os from enum import Enumclass LaneDirectionType(int, Enum):LaneDirectionType_Unknown -1 # 类型未知OneWay 1 # 单向TwoWay 2 # 双向# 颜色类型 class ColorCombo(int, Enum):NOUSE 0 # 默认值UNKNOWN 1000 # 未定义WHITE 1 # 白色(默认值…
阅读更多...
俄罗斯套娃 (Matryoshka) 嵌入模型概述

俄罗斯套娃 (Matryoshka) 嵌入模型概述

在这篇博客中&#xff0c;我们将向你介绍俄罗斯套娃嵌入的概念&#xff0c;并解释为什么它们很有用。我们将讨论这些模型在理论上是如何训练的&#xff0c;以及你如何使用 Sentence Transformers 来训练它们。 除此之外&#xff0c;我们还会告诉你怎么用这种像套娃一样的俄罗斯…
阅读更多...
【Vue】vue3 在图片上渲染 OCR 识别后的文本框、可复制文本组件

【Vue】vue3 在图片上渲染 OCR 识别后的文本框、可复制文本组件

需求 后面返回解析后的文本和四角坐标&#xff0c;在图片上渲染成框&#xff0c;并且可复制。图片还可以缩放、拖拽 实现 这里要重点讲下关于OCR文本框的处理&#xff1a; 因为一些文字可能是斜着放的&#xff0c;所有我们要特殊处理&#xff0c;根据三角函数来计算出它的偏…
阅读更多...
分布式ID生成策略-雪花算法Snowflake

分布式ID生成策略-雪花算法Snowflake

分布式ID生成策略-雪花算法Snowflake 一、其他分布式ID策略1.UUID2.数据库自增与优化2.1 优化1 - 共用id自增表2.2 优化2 - 分段获取id 3.Reids的incr和incrby 二、雪花算法Snowflake1.雪花算法的定义2.基础雪花算法源码解读3.并发1000测试4.如何设置机房和机器id4.雪花算法时钟…
阅读更多...
短剧系统开发：一种新型的娱乐方式

短剧系统开发：一种新型的娱乐方式

一、引言 随着科技的快速发展&#xff0c;人们的生活方式也在逐渐改变。在娱乐领域&#xff0c;短剧作为一种新型的娱乐方式&#xff0c;正在受到越来越多人的喜爱。短剧以其短小精悍、情节紧凑、易于观看等特点&#xff0c;迅速占领了市场。因此&#xff0c;开发一款短剧系统…
阅读更多...
基于STC12C5A60S2系列1T 8051单片机的TM1638键盘数码管模块的数码管显示应用

基于STC12C5A60S2系列1T 8051单片机的TM1638键盘数码管模块的数码管显示应用

基于STC12C5A60S2系列1T 8051单片机的TM1638键盘数码管模块的数码管显示应用 STC12C5A60S2系列1T 8051单片机管脚图STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式及配置STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式介绍TM1638键盘数码管模块概述TM1638键盘数码管…
阅读更多...
pytorch什么是梯度

pytorch什么是梯度

目录 1.导数、偏微分、梯度1.1 导数1.2 偏微分1.3 梯度 2. 通过梯度求极小值3. learning rate3. 局部最小值4. Saddle point鞍点 1.导数、偏微分、梯度 1.1 导数 对于yx 2 2 2 的导数&#xff0c;描述了y随x值变化的一个变化趋势&#xff0c;导数是个标量反应的是变化的程度&…
阅读更多...
NoSQL--3.MongoDB配置（Linux版）

NoSQL--3.MongoDB配置（Linux版）

目录 2.2 Linux环境下操作 2.2.1 传输MongoDB压缩包到虚拟机&#xff1a; 2.2.2 启动MongoDB服务&#xff1a; 2.2 Linux环境下操作 2.2.1 传输MongoDB压缩包到虚拟机&#xff1a; &#xff08;笔者使用XShell传输&#xff09; 如果不想放在如图的路径&#xff0c;删除操作…
阅读更多...
基于springboot+vue实现学校田径运动会系统项目【项目源码+论文说明】计算机毕业设计

基于springboot+vue实现学校田径运动会系统项目【项目源码+论文说明】计算机毕业设计

基于springbootvue实现学校田径运动会系统演示 摘要 随着互联网普及率的提高&#xff0c;互联网与人们日常生活的关系越来越密切&#xff0c;越来越多学校也正在着力建设自己的信息化管理系统&#xff0c;学校根据自身的发展及社会发展的需要&#xff0c;开始将传统的运动会成…
阅读更多...
Golang模糊测试实践

Golang模糊测试实践

模糊测试可以简单快速的自动化构建测试用例&#xff0c;尽量遍历各种可能的输入场景&#xff0c;从而保证函数代码覆盖尽可能多的边缘场景。Go原生内置了模糊测试的支持&#xff0c;如果善加利用&#xff0c;可以有效提升Go代码的质量。原文: Fuzz Testing in Golang 题图由Lex…
阅读更多...
Hadoop配置日志的聚集——jobhistory不显示任务问题

Hadoop配置日志的聚集——jobhistory不显示任务问题

问题&#xff1a; 一开始job history是正常的&#xff0c;配置了日志的聚集以后不管做什么任务都不显示任务&#xff0c;hdfs是正常运行&#xff0c;而且根据配置步骤都重启过了。 下面先po出日志聚集的操作步骤&#xff0c;再讲问题 1.配置yarn-site.xml cd $HADOOP_HOME/e…
阅读更多...
0基础跨考408｜一战上岸复盘及经验分享

0基础跨考408｜一战上岸复盘及经验分享

基础阶段‼️ 王道的四本书的选择题部分要都做完、订正完。 王道的四门视频课要一轮刷完&#xff08;或者题主在B站看了其他的老师&#xff0c;这其实也是算一轮的&#xff0c;只要题主是认真学习了的&#xff0c;题主说自己不知道看什么课&#xff0c;王道就好了&#xff09;…
阅读更多...
kibana配置 dashbord，做可视化展示

kibana配置 dashbord，做可视化展示

一、环境介绍 这里我使用的kibana版本为7.17版本。 语言选择为中文。 需要已经有es&#xff0c;已经有kibana&#xff0c;并且都能正常访问。 二、背景介绍 kibana的可视化界面&#xff0c;可以配置很多监控统计界面。非常方便&#xff0c;做数据的可视化展示。 这篇文章&…
阅读更多...
【四】【SQL Server】如何运用SQL Server中查询设计器通关数据库期末查询大题

【四】【SQL Server】如何运用SQL Server中查询设计器通关数据库期末查询大题

数据库学生选择1122 数据库展示 course表展示 SC表展示 student表展示 数据库学生选课1122_3 第十一题 第十二题 第十三题 第十四题 第十五题 数据库学生选课1122_4 第十六题 第十七题 第十八题 第十九题 第二十题 数据库学生选课1122_5 第二十一题 第二十二题 结尾 最后&…
阅读更多...
恒驰上云规划实施解决方案上线华为云官网

恒驰上云规划实施解决方案上线华为云官网

华为云与伙伴共同打造联合解决方案 已成为更多企业的数字化转型利器 1月恒驰上云规划实施解决方案 完成上市宣讲并正式上架华为云官网 恒驰上云规划实施解决方案能力全景图&#xff1a;融合厂商云服务能力&#xff0c;一站式高效云迁移 从深入了解企业的本地IT环境、业务特点…
阅读更多...
查看kafka消息消费堆积情况

查看kafka消息消费堆积情况

查看主题命令 展示topic列表 ./kafka-topics.sh --list --zookeeper zookeeper_ip:2181描述topic ./kafka-topics.sh --describe --zookeeper zookeeper_ip:2181 --topic topic_name查看topic某分区偏移量最大&#xff08;小&#xff09;值 ./kafka-run-class.sh kafka.too…
阅读更多...
Git——Upload your open store

Git——Upload your open store

0.default config ssh-keygen -t rsa #之后一路回车,当前目录.ssh/下产生公私钥 cat ~/.ssh/id_rsa.pub #复制公钥到账号 git config --global user.email account_email git config --global user.name account_name1. 上传一个公开仓库 查看当前分支&#xff1a; git branc…
阅读更多...
JavaSE——基础小项目-模拟ATM系统（项目主要目标、技术选型、架构搭建、具体实现、完整代码注释）

JavaSE——基础小项目-模拟ATM系统（项目主要目标、技术选型、架构搭建、具体实现、完整代码注释）

目录 项目主要目标 技术选型 面向对象编程 使用集合容器 程序流程控制 使用常见API 系统架构搭建与欢迎页设计 Account ATM Test 用户开户功能实现 录入账户名称与性别 录入账户密码与取现额度 生成新卡号 存入账户 登录功能实现 登录后操作实现 退出账户 存…
阅读更多...
最新文章

Copyright @ 2022~2023