【树上倍增】【割点】 【换根法】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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255

测试用例

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);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

换根法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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

割点

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

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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315

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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397

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