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

作者保举

视频算法专题
本文涉及知识点

树上倍增 树 图论 并集查找 换根法 深度优先
割点原理及封装好的割点类(预计2024年3月11号左右发布）
LeetCode3067. 在带权树网络中统计可连接服务器对数量

给你一棵无根带权树，树中总共有 n 个节点，分别表现 n 个服务器，服务器从 0 到 n - 1 编号。同时给你一个数组 edges ，其中 edges = [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 可连接 的服务器对的 数量 。
示例 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.length == 3
0 <= ai, bi < n
edges = [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)。
并集查找

1. class CNeiBo
2. {
3. public:       
4.         static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
5.         {
6.                 vector<vector<int>>  vNeiBo(n);
7.                 for (const auto& v : edges)
8.                 {
9.                         vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
10.                         if (!bDirect)
11.                         {
12.                                 vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
13.                         }
14.                 }
15.                 return vNeiBo;
16.         }       
17.         static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
18.         {
19.                 vector<vector<std::pair<int, int>>> vNeiBo(n);
20.                 for (const auto& v : edges)
21.                 {
22.                         vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
23.                         if (!bDirect)
24.                         {
25.                                 vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
26.                         }
27.                 }
28.                 return vNeiBo;
29.         }
30. };
31. class CUnionFind
32. {
33. public:
34.         CUnionFind(int iSize) :m_vNodeToRegion(iSize)
35.         {
36.                 for (int i = 0; i < iSize; i++)
37.                 {
38.                         m_vNodeToRegion[i] = i;
39.                 }
40.                 m_iConnetRegionCount = iSize;
41.         }       
42.         CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
43.         {
44.                 for (int i = 0; i < vNeiBo.size(); i++) {
45.                         for (const auto& n : vNeiBo[i]) {
46.                                 Union(i, n);
47.                         }
48.                 }
49.         }
50.         int GetConnectRegionIndex(int iNode)
51.         {
52.                 int& iConnectNO = m_vNodeToRegion[iNode];
53.                 if (iNode == iConnectNO)
54.                 {
55.                         return iNode;
56.                 }
57.                 return iConnectNO = GetConnectRegionIndex(iConnectNO);
58.         }
59.         void Union(int iNode1, int iNode2)
60.         {
61.                 const int iConnectNO1 = GetConnectRegionIndex(iNode1);
62.                 const int iConnectNO2 = GetConnectRegionIndex(iNode2);
63.                 if (iConnectNO1 == iConnectNO2)
64.                 {
65.                         return;
66.                 }
67.                 m_iConnetRegionCount--;
68.                 if (iConnectNO1 > iConnectNO2)
69.                 {
70.                         UnionConnect(iConnectNO1, iConnectNO2);
71.                 }
72.                 else
73.                 {
74.                         UnionConnect(iConnectNO2, iConnectNO1);
75.                 }
76.         }
78.         bool IsConnect(int iNode1, int iNode2)
79.         {
80.                 return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
81.         }
82.         int GetConnetRegionCount()const
83.         {
84.                 return m_iConnetRegionCount;
85.         }
86.         vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
87.         {
88.                 const int iNodeSize = m_vNodeToRegion.size();
89.                 vector<int> vRet(iNodeSize);
90.                 for (int i = 0; i < iNodeSize; i++)
91.                 {
92.                         vRet[GetConnectRegionIndex(i)]++;
93.                 }
94.                 return vRet;
95.         }
96.         std::unordered_map<int, vector<int>> GetNodeOfRegion()
97.         {
98.                 std::unordered_map<int, vector<int>> ret;
99.                 const int iNodeSize = m_vNodeToRegion.size();
100.                 for (int i = 0; i < iNodeSize; i++)
101.                 {
102.                         ret[GetConnectRegionIndex(i)].emplace_back(i);
103.                 }
104.                 return ret;
105.         }
106. private:
107.         void UnionConnect(int iFrom, int iTo)
108.         {
109.                 m_vNodeToRegion[iFrom] = iTo;
110.         }
111.         vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
112.         int m_iConnetRegionCount;
113. };
115. class CParents
116. {
117. public:
118.         CParents(vector<int>& vParent, const vector<int>& vLeve):m_vLeve(vLeve)
119.         {
120.                 const int iMaxLeve = *std::max_element(vLeve.begin(), vLeve.end());
121.                 int iBitNum = 0;
122.                 for (; (1 << iBitNum) < iMaxLeve; iBitNum++);
123.                 const int n = vParent.size();
124.                 m_vParents.assign(iBitNum+1, vector<int>(n, -1));
125.                 m_vParents[0] = vParent;
126.                 //树上倍增
127.                 for (int i = 1; i < m_vParents.size(); i++)
128.                 {
129.                         for (int j = 0; j < n; j++)
130.                         {
131.                                 const int iPre = m_vParents[i - 1][j];
132.                                 if (-1 != iPre)
133.                                 {
134.                                         m_vParents[i][j] = m_vParents[i - 1][iPre];
135.                                 }
136.                         }
137.                 }
138.         }
139.         int GetParent(int iNode, int iLeve)const
140.         {
141.                 int iParent = iNode;
142.                 for (int iBit = 0; iBit < m_vParents.size(); iBit++)
143.                 {
144.                         if (-1 == iParent)
145.                         {
146.                                 return iParent;
147.                         }
148.                         if (iLeve & (1 << iBit))
149.                         {
150.                                 iParent = m_vParents[iBit][iParent];
151.                         }
152.                 }
153.                 return iParent;
154.         }
155.         int GetPublicParent(int iNode1, int iNode2)const
156.         {
157.                 int leve0 = m_vLeve[iNode1];
158.                 int leve1 = m_vLeve[iNode2];
159.                 if (leve0 < leve1)
160.                 {
161.                         iNode2 = GetParent(iNode2, leve1 - leve0);
162.                         leve1 = leve0;
163.                 }
164.                 else
165.                 {
166.                         iNode1 = GetParent(iNode1, leve0 - leve1);
167.                         leve0 = leve1;
168.                 }
169.                 //二分查找
170.                 int left = -1, r = leve0;
171.                 while (r - left > 1)
172.                 {
173.                         const auto mid = left + (r - left) / 2;
174.                         const int iParent0 = GetParent(iNode1, mid);
175.                         const int iParent1 = GetParent(iNode2, mid);
176.                         if (iParent0 == iParent1)
177.                         {
178.                                 r = mid;
179.                         }
180.                         else
181.                         {
182.                                 left = mid;
183.                         }
184.                 }
185.                 return GetParent(iNode1, r);
186.         }
187. protected:
188.         vector<vector<int>> m_vParents;
189.         const vector<int> m_vLeve;
190. };
192. class Solution {
193. public:
194.         vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
195.                 m_c = edges.size() + 1;
196.                 m_vDisToRoot.resize(m_c);
197.                 m_vParent.resize(m_c);
198.                 m_vLeve.resize(m_c);
199.                 auto neiBo = CNeiBo::Three(m_c, edges, false, 0);
200.                 DFS(neiBo, 0, -1, 0,0);       
201.                 CParents par(m_vParent,m_vLeve);
202.                 vector<int> vRet(m_c);
203.                 for (int c = 0; c < m_c; c++)
204.                 {
205.                         CUnionFind uf(m_c);
206.                         for (const auto& v : edges)
207.                         {
208.                                 if ((v[0] == c) || (v[1] == c))
209.                                 {
210.                                         continue;
211.                                 }
212.                                 uf.Union(v[0], v[1]);
213.                         }
214.                         vector<int> vRegionCnt(m_c);
215.                         for (int ab = 0; ab < m_c; ab++)
216.                         {
217.                                 if (ab == c )
218.                                 {
219.                                         continue;
220.                                 }
221.                                 const int pub = par.GetPublicParent(ab, c);
222.                                 const int len = m_vDisToRoot[ab] + m_vDisToRoot[c] - 2 * m_vDisToRoot[pub];
223.                                 if (0 != len % signalSpeed)
224.                                 {
225.                                         continue;
226.                                 }
227.                                 vRegionCnt[uf.GetConnectRegionIndex(ab)]++;
228.                         }
229.                         int&iRet = vRet[c];
230.                         const int total = std::accumulate(vRegionCnt.begin(), vRegionCnt.end(), 0);
231.                         for (int c1 = 0; c1 < m_c; c1++)
232.                         {
233.                                 iRet += vRegionCnt[c1] * (total - vRegionCnt[c1]);
234.                         }       
235.                         iRet /= 2;
236.                 }
237.                 return vRet;
238.         }
239.         void DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par,int leve,int dis)
240.         {
241.                 m_vDisToRoot[cur] =dis;
242.                 m_vParent[cur] = par;
243.                 m_vLeve[cur] = leve;
244.                 for (const auto& [next,len] : neiBo[cur])
245.                 {
246.                         if (next == par)
247.                         {
248.                                 continue;
249.                         }
250.                         DFS(neiBo, next, cur,leve+1,dis+len);
251.                 }
252.         }
253.         vector<int> m_vDisToRoot,m_vParent,m_vLeve;
254.         int m_c;
255. };

复制代码

测试用例

1. template<class T,class T2>
2. void Assert(const T& t1, const T2& t2)
3. {
4.         assert(t1 == t2);
5. }
7. template<class T>
8. void Assert(const vector<T>& v1, const vector<T>& v2)
9. {
10.         if (v1.size() != v2.size())
11.         {
12.                 assert(false);
13.                 return;
14.         }
15.         for (int i = 0; i < v1.size(); i++)
16.         {
17.                 Assert(v1[i], v2[i]);
18.         }
20. }
22. int main()
23. {
24.         vector<vector<int>> edges;
25.         int signalSpeed;
26.         {
27.                 Solution sln;
28.                 edges = {  }, signalSpeed = 1;
29.                 auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
30.                 Assert({ 0 }, res);
31.         }
32.         {
33.                 Solution sln;
34.                 edges = { {0,1,1} }, signalSpeed = 1;
35.                 auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
36.                 Assert({ 0,0 }, res);
37.         }
38.         {
39.                 Solution sln;
40.                 edges = { {0,1,1},{1,2,1} }, signalSpeed = 1;
41.                 auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
42.                 Assert({ 0,1,0 }, res);
43.         }
44.         {
45.                 Solution sln;
46.                 edges = { {0,1,1},{1,2,5},{2,3,13},{3,4,9},{4,5,2} }, signalSpeed = 1;
47.                 auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
48.                 Assert({ 0,4,6,6,4,0 } , res);
49.         }
50.         {
51.                 Solution sln;
52.                 edges = { {0,6,3},{6,5,3},{0,3,1},{3,2,7},{3,1,6},{3,4,2} }, signalSpeed = 3;
53.                 auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
54.                 Assert({ 2,0,0,0,0,0,2 }, res);
55.         }
56. }

复制代码

换根法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)只取一个。

1. class CNeiBo
2. {
3. public:       
4.         static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
5.         {
6.                 vector<vector<int>>  vNeiBo(n);
7.                 for (const auto& v : edges)
8.                 {
9.                         vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
10.                         if (!bDirect)
11.                         {
12.                                 vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
13.                         }
14.                 }
15.                 return vNeiBo;
16.         }       
17.         static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
18.         {
19.                 vector<vector<std::pair<int, int>>> vNeiBo(n);
20.                 for (const auto& v : edges)
21.                 {
22.                         vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
23.                         if (!bDirect)
24.                         {
25.                                 vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
26.                         }
27.                 }
28.                 return vNeiBo;
29.         }
30. };
32. class Solution {
33. public:
34.         vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
35.                 m_c = edges.size() + 1;
36.                 m_iSignalSpeed = signalSpeed;               
37.                 auto neiBo = CNeiBo::Three(m_c, edges, false, 0);               
38.                 vector<int> vRet(m_c);
39.                 for (int c = 0; c < m_c; c++)
40.                 {
41.                         int& iRet = vRet[c];
42.                         int left = 0;
43.                         for (const auto& [next, len] : neiBo[c])
44.                         {
45.                                 int cur = DFS(neiBo, next, c, len);
46.                                 iRet += left * cur;
47.                                 left += cur;
48.                         }
49.                 }
50.                 return vRet;
51.         }
52.         int DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par,int dis)
53.         {
54.                 int iRet = (0 ==dis % m_iSignalSpeed);
55.                 for (const auto& [next,len] : neiBo[cur])
56.                 {
57.                         if (next == par)
58.                         {
59.                                 continue;
60.                         }
61.                         iRet +=DFS(neiBo, next, cur,dis+len);
62.                 }
63.                 return iRet;
64.         }
65.         int m_iSignalSpeed;
66.         int m_c;
67. };

复制代码

割点

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

1. class CNeiBo
2. {
3. public:       
4.         static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
5.         {
6.                 vector<vector<int>>  vNeiBo(n);
7.                 for (const auto& v : edges)
8.                 {
9.                         vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
10.                         if (!bDirect)
11.                         {
12.                                 vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
13.                         }
14.                 }
15.                 return vNeiBo;
16.         }       
17.         static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
18.         {
19.                 vector<vector<std::pair<int, int>>> vNeiBo(n);
20.                 for (const auto& v : edges)
21.                 {
22.                         vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
23.                         if (!bDirect)
24.                         {
25.                                 vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
26.                         }
27.                 }
28.                 return vNeiBo;
29.         }
30. };
31. class CUnionFind
32. {
33. public:
34.         CUnionFind(int iSize) :m_vNodeToRegion(iSize)
35.         {
36.                 for (int i = 0; i < iSize; i++)
37.                 {
38.                         m_vNodeToRegion[i] = i;
39.                 }
40.                 m_iConnetRegionCount = iSize;
41.         }       
42.         CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
43.         {
44.                 for (int i = 0; i < vNeiBo.size(); i++) {
45.                         for (const auto& n : vNeiBo[i]) {
46.                                 Union(i, n);
47.                         }
48.                 }
49.         }
50.         int GetConnectRegionIndex(int iNode)
51.         {
52.                 int& iConnectNO = m_vNodeToRegion[iNode];
53.                 if (iNode == iConnectNO)
54.                 {
55.                         return iNode;
56.                 }
57.                 return iConnectNO = GetConnectRegionIndex(iConnectNO);
58.         }
59.         void Union(int iNode1, int iNode2)
60.         {
61.                 const int iConnectNO1 = GetConnectRegionIndex(iNode1);
62.                 const int iConnectNO2 = GetConnectRegionIndex(iNode2);
63.                 if (iConnectNO1 == iConnectNO2)
64.                 {
65.                         return;
66.                 }
67.                 m_iConnetRegionCount--;
68.                 if (iConnectNO1 > iConnectNO2)
69.                 {
70.                         UnionConnect(iConnectNO1, iConnectNO2);
71.                 }
72.                 else
73.                 {
74.                         UnionConnect(iConnectNO2, iConnectNO1);
75.                 }
76.         }
78.         bool IsConnect(int iNode1, int iNode2)
79.         {
80.                 return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
81.         }
82.         int GetConnetRegionCount()const
83.         {
84.                 return m_iConnetRegionCount;
85.         }
86.         vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
87.         {
88.                 const int iNodeSize = m_vNodeToRegion.size();
89.                 vector<int> vRet(iNodeSize);
90.                 for (int i = 0; i < iNodeSize; i++)
91.                 {
92.                         vRet[GetConnectRegionIndex(i)]++;
93.                 }
94.                 return vRet;
95.         }
96.         std::unordered_map<int, vector<int>> GetNodeOfRegion()
97.         {
98.                 std::unordered_map<int, vector<int>> ret;
99.                 const int iNodeSize = m_vNodeToRegion.size();
100.                 for (int i = 0; i < iNodeSize; i++)
101.                 {
102.                         ret[GetConnectRegionIndex(i)].emplace_back(i);
103.                 }
104.                 return ret;
105.         }
106. private:
107.         void UnionConnect(int iFrom, int iTo)
108.         {
109.                 m_vNodeToRegion[iFrom] = iTo;
110.         }
111.         vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
112.         int m_iConnetRegionCount;
113. };
115. class CParents
116. {
117. public:
118.         CParents(vector<int>& vParent, const int iMaxLeve)
119.         {       
120.                 int iBitNum = 0;
121.                 for (; (1 << iBitNum) < iMaxLeve; iBitNum++);
122.                 const int n = vParent.size();
123.                 m_vParents.assign(iBitNum+1, vector<int>(n, -1));
124.                 m_vParents[0] = vParent;
125.                 //树上倍增
126.                 for (int i = 1; i < m_vParents.size(); i++)
127.                 {
128.                         for (int j = 0; j < n; j++)
129.                         {
130.                                 const int iPre = m_vParents[i - 1][j];
131.                                 if (-1 != iPre)
132.                                 {
133.                                         m_vParents[i][j] = m_vParents[i - 1][iPre];
134.                                 }
135.                         }
136.                 }
137.         }
138.         int GetParent(int iNode, int iLeve)const
139.         {
140.                 int iParent = iNode;
141.                 for (int iBit = 0; iBit < m_vParents.size(); iBit++)
142.                 {
143.                         if (-1 == iParent)
144.                         {
145.                                 return iParent;
146.                         }
147.                         if (iLeve & (1 << iBit))
148.                         {
149.                                 iParent = m_vParents[iBit][iParent];
150.                         }
151.                 }
152.                 return iParent;
153.         }       
154. protected:
155.         vector<vector<int>> m_vParents;
156. };
158. class C2Parents : CParents
159. {
160. public:
161.         C2Parents(vector<int>& vParent, const vector<int>& vLeve) :m_vLeve(vLeve)
162.                 , CParents(vParent,*std::max_element(vLeve.begin(), vLeve.end()))
163.         {               
164.         }       
165.         int GetPublicParent(int iNode1, int iNode2)const
166.         {
167.                 int leve0 = m_vLeve[iNode1];
168.                 int leve1 = m_vLeve[iNode2];
169.                 if (leve0 < leve1)
170.                 {
171.                         iNode2 = GetParent(iNode2, leve1 - leve0);
172.                         leve1 = leve0;
173.                 }
174.                 else
175.                 {
176.                         iNode1 = GetParent(iNode1, leve0 - leve1);
177.                         leve0 = leve1;
178.                 }
179.                 //二分查找
180.                 int left = -1, r = leve0;
181.                 while (r - left > 1)
182.                 {
183.                         const auto mid = left + (r - left) / 2;
184.                         const int iParent0 = GetParent(iNode1, mid);
185.                         const int iParent1 = GetParent(iNode2, mid);
186.                         if (iParent0 == iParent1)
187.                         {
188.                                 r = mid;
189.                         }
190.                         else
191.                         {
192.                                 left = mid;
193.                         }
194.                 }
195.                 return GetParent(iNode1, r);
196.         }
197. protected:
199.         vector<vector<int>> m_vParents;
200.         const vector<int> m_vLeve;
201. };
203. class CCutPointEx
204. {
205. public:
206.         CCutPointEx(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
207.         {
208.                 m_vNodeToTime.assign(m_iSize, -1);
209.                 m_vChildFirstEnd.resize(m_iSize);
210.                 m_vNodeToRegion.assign(m_iSize, -1);
211.                 m_vCut.assign(m_iSize, false);
212.                 for (int i = 0; i < m_iSize; i++)
213.                 {
214.                         if (-1 != m_vNodeToTime[i])
215.                         {
216.                                 continue;
217.                         }
218.                         dfs(i, -1, vNeiB);
219.                         m_iRegionCount++;
220.                 }
221.                 m_vTimeToNode.resize(m_iSize);
222.                 for (int i = 0; i < m_iSize; i++)
223.                 {
224.                         m_vTimeToNode[m_vNodeToTime[i]] = i;;
225.                 }
226.         }
227.         bool Visit(int src, int dest, int iCut)const
228.         {
229.                 if (m_vNodeToRegion[src] != m_vNodeToRegion[dest])
230.                 {
231.                         return false;//不在一个连通区域
232.                 }
233.                 if (!m_vCut[iCut])
234.                 {
235.                         return true;
236.                 }
237.                 const int r1 = GetCutRegion(iCut, src);
238.                 const int r2 = GetCutRegion(iCut, dest);
239.                 return r1 == r2;
240.         }
241.         vector<vector<int>> GetSubRegionOfCut(const int iCut)const
242.         {//删除iCut及和它相连的边后，iCut所在的区域会分成几个区域：父节点一个区域、各子节点一个区域
243.          //父节点所在区域可能为空，如果iCut所在的连通区域只有一个节点，则返回一个没有节点的区域。
244.                 const auto& v = m_vChildFirstEnd[iCut];
245.                 vector<vector<int>> vRet(1);                       
246.                 int j = 0;
247.                 for (int iTime=0;iTime < m_iSize; iTime++ )
248.                 {
249.                         const int iNode        = m_vTimeToNode[iTime];
250.                         if ((j < v.size()) && ( iTime  >= v[j].first ))
251.                         {
252.                                 j++;
253.                                 vRet.emplace_back();
254.                         }
255.                         if ((iCut != iNode) && (m_vNodeToRegion[iNode] == m_vNodeToRegion[iCut]))
256.                         {
257.                                 if (v.size()&&(iTime >= v.back().second))
258.                                 {
259.                                         vRet[0].emplace_back(iNode);
260.                                 }
261.                                 else
262.                                 {
263.                                         vRet.back().emplace_back(iNode);
264.                                 }
265.                         }
266.                 }
267.                 return vRet;
268.         }
269. protected:
270.         int dfs(int cur, int parent, const vector<vector<int>>& vNeiB)
271.         {
272.                 auto& curTime = m_vNodeToTime[cur];
273.                 m_vNodeToRegion[cur] = m_iRegionCount;
274.                 curTime = m_iTime++;
275.                 int iCutChild = 0;
276.                 int iMinTime = curTime;
277.                 for (const auto& next : vNeiB[cur])
278.                 {
279.                         if (-1 != m_vNodeToTime[next])
280.                         {
281.                                 iMinTime = min(iMinTime, m_vNodeToTime[next]);
282.                                 continue;
283.                         }
284.                         int iChildBeginTime = m_iTime;
285.                         const int iChildMinTime = dfs(next, cur, vNeiB);
286.                         iMinTime = min(iMinTime, iChildMinTime);
287.                         if (iChildMinTime >= curTime)
288.                         {
289.                                 iCutChild++;
290.                                 m_vChildFirstEnd[cur].push_back({ iChildBeginTime,m_iTime });
291.                         };
292.                 }
293.                 m_vCut[cur] = (iCutChild + (-1 != parent)) >= 2;
294.                 return iMinTime;
295.         }
296.         int GetCutRegion(int iCut, int iNode)const
297.         {
298.                 const auto& v = m_vChildFirstEnd[iCut];
299.                 auto it = std::upper_bound(v.begin(), v.end(), m_vNodeToTime[iNode], [](int time, const std::pair<int, int>& pr) {return time < pr.first; });
300.                 if (v.begin() == it)
301.                 {
302.                         return v.size();
303.                 }
304.                 --it;
305.                 return (it->second > m_vNodeToTime[iNode]) ? (it - v.begin()) : v.size();
306.         }
307.         int m_iTime = 0;
308.         const int m_iSize;//时间戳
309.         int m_iRegionCount = 0;
310.         vector<int> m_vNodeToTime;//各节点到达时间，从0开始。 -1表示未处理
311.         vector<bool> m_vCut;//是否是割点
312.         vector<int> m_vNodeToRegion;//各节点所在区域
313.         vector<vector<pair<int, int>>> m_vChildFirstEnd;//左闭右开空间[0,m_vChildFirstEnd[0].first)和[m_vChildFirstEnd.back().second,iSize)是一个区域
314.         vector<int> m_vTimeToNode;
315. };

复制代码

2024年3月9号 新封装

1. class CNeiBo
2. {
3. public:       
4.         static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
5.         {
6.                 vector<vector<int>>  vNeiBo(n);
7.                 for (const auto& v : edges)
8.                 {
9.                         vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
10.                         if (!bDirect)
11.                         {
12.                                 vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
13.                         }
14.                 }
15.                 return vNeiBo;
16.         }       
17.         static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
18.         {
19.                 vector<vector<std::pair<int, int>>> vNeiBo(n);
20.                 for (const auto& v : edges)
21.                 {
22.                         vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
23.                         if (!bDirect)
24.                         {
25.                                 vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
26.                         }
27.                 }
28.                 return vNeiBo;
29.         }
30. };
31. class CUnionFind
32. {
33. public:
34.         CUnionFind(int iSize) :m_vNodeToRegion(iSize)
35.         {
36.                 for (int i = 0; i < iSize; i++)
37.                 {
38.                         m_vNodeToRegion[i] = i;
39.                 }
40.                 m_iConnetRegionCount = iSize;
41.         }       
42.         CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
43.         {
44.                 for (int i = 0; i < vNeiBo.size(); i++) {
45.                         for (const auto& n : vNeiBo[i]) {
46.                                 Union(i, n);
47.                         }
48.                 }
49.         }
50.         int GetConnectRegionIndex(int iNode)
51.         {
52.                 int& iConnectNO = m_vNodeToRegion[iNode];
53.                 if (iNode == iConnectNO)
54.                 {
55.                         return iNode;
56.                 }
57.                 return iConnectNO = GetConnectRegionIndex(iConnectNO);
58.         }
59.         void Union(int iNode1, int iNode2)
60.         {
61.                 const int iConnectNO1 = GetConnectRegionIndex(iNode1);
62.                 const int iConnectNO2 = GetConnectRegionIndex(iNode2);
63.                 if (iConnectNO1 == iConnectNO2)
64.                 {
65.                         return;
66.                 }
67.                 m_iConnetRegionCount--;
68.                 if (iConnectNO1 > iConnectNO2)
69.                 {
70.                         UnionConnect(iConnectNO1, iConnectNO2);
71.                 }
72.                 else
73.                 {
74.                         UnionConnect(iConnectNO2, iConnectNO1);
75.                 }
76.         }
78.         bool IsConnect(int iNode1, int iNode2)
79.         {
80.                 return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
81.         }
82.         int GetConnetRegionCount()const
83.         {
84.                 return m_iConnetRegionCount;
85.         }
86.         vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
87.         {
88.                 const int iNodeSize = m_vNodeToRegion.size();
89.                 vector<int> vRet(iNodeSize);
90.                 for (int i = 0; i < iNodeSize; i++)
91.                 {
92.                         vRet[GetConnectRegionIndex(i)]++;
93.                 }
94.                 return vRet;
95.         }
96.         std::unordered_map<int, vector<int>> GetNodeOfRegion()
97.         {
98.                 std::unordered_map<int, vector<int>> ret;
99.                 const int iNodeSize = m_vNodeToRegion.size();
100.                 for (int i = 0; i < iNodeSize; i++)
101.                 {
102.                         ret[GetConnectRegionIndex(i)].emplace_back(i);
103.                 }
104.                 return ret;
105.         }
106. private:
107.         void UnionConnect(int iFrom, int iTo)
108.         {
109.                 m_vNodeToRegion[iFrom] = iTo;
110.         }
111.         vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
112.         int m_iConnetRegionCount;
113. };
115. class CParents
116. {
117. public:
118.         CParents(vector<int>& vParent, const int iMaxLeve)
119.         {       
120.                 int iBitNum = 0;
121.                 for (; (1 << iBitNum) < iMaxLeve; iBitNum++);
122.                 const int n = vParent.size();
123.                 m_vParents.assign(iBitNum+1, vector<int>(n, -1));
124.                 m_vParents[0] = vParent;
125.                 //树上倍增
126.                 for (int i = 1; i < m_vParents.size(); i++)
127.                 {
128.                         for (int j = 0; j < n; j++)
129.                         {
130.                                 const int iPre = m_vParents[i - 1][j];
131.                                 if (-1 != iPre)
132.                                 {
133.                                         m_vParents[i][j] = m_vParents[i - 1][iPre];
134.                                 }
135.                         }
136.                 }
137.         }
138.         int GetParent(int iNode, int iLeve)const
139.         {
140.                 int iParent = iNode;
141.                 for (int iBit = 0; iBit < m_vParents.size(); iBit++)
142.                 {
143.                         if (-1 == iParent)
144.                         {
145.                                 return iParent;
146.                         }
147.                         if (iLeve & (1 << iBit))
148.                         {
149.                                 iParent = m_vParents[iBit][iParent];
150.                         }
151.                 }
152.                 return iParent;
153.         }       
154. protected:
155.         vector<vector<int>> m_vParents;
156. };
158. class C2Parents : CParents
159. {
160. public:
161.         C2Parents(vector<int>& vParent, const vector<int>& vLeve) :m_vLeve(vLeve)
162.                 , CParents(vParent,*std::max_element(vLeve.begin(), vLeve.end()))
163.         {               
164.         }       
165.         int GetPublicParent(int iNode1, int iNode2)const
166.         {
167.                 int leve0 = m_vLeve[iNode1];
168.                 int leve1 = m_vLeve[iNode2];
169.                 if (leve0 < leve1)
170.                 {
171.                         iNode2 = GetParent(iNode2, leve1 - leve0);
172.                         leve1 = leve0;
173.                 }
174.                 else
175.                 {
176.                         iNode1 = GetParent(iNode1, leve0 - leve1);
177.                         leve0 = leve1;
178.                 }
179.                 //二分查找
180.                 int left = -1, r = leve0;
181.                 while (r - left > 1)
182.                 {
183.                         const auto mid = left + (r - left) / 2;
184.                         const int iParent0 = GetParent(iNode1, mid);
185.                         const int iParent1 = GetParent(iNode2, mid);
186.                         if (iParent0 == iParent1)
187.                         {
188.                                 r = mid;
189.                         }
190.                         else
191.                         {
192.                                 left = mid;
193.                         }
194.                 }
195.                 return GetParent(iNode1, r);
196.         }
197. protected:
199.         vector<vector<int>> m_vParents;
200.         const vector<int> m_vLeve;
201. };
203. //割点
204. class CCutPoint
205. {
206. public:
207.         CCutPoint(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
208.         {
209.                 m_vNodeToTime.assign(m_iSize, -1);
210.                 m_vCutNewRegion.resize(m_iSize);
211.                 for (int i = 0; i < m_iSize; i++)
212.                 {
213.                         if (-1 == m_vNodeToTime[i])
214.                         {
215.                                 m_vRegionFirstTime.emplace_back(m_iTime);
216.                                 dfs(vNeiB, i, -1);
217.                         }
218.                 }       
219.         }
220.         int dfs(const vector<vector<int>>& vNeiB,const int cur, const int parent)
221.         {
222.                 int iMinTime = m_vNodeToTime[cur] = m_iTime++;
223.                 int iRegionCount = (-1 != parent);//根连通区域数量
224.                 for (const auto& next : vNeiB[cur])                {
225.                         if (-1  != m_vNodeToTime[next])                        {
226.                                 iMinTime = min(iMinTime, m_vNodeToTime[next]);
227.                                 continue;
228.                         }
229.                         const int childMinTime = dfs(vNeiB, next, cur);
230.                         iMinTime = min(iMinTime, childMinTime);
231.                         if (childMinTime >= m_vNodeToTime[cur])                        {
232.                                 iRegionCount++;
233.                                 m_vCutNewRegion[cur].emplace_back(m_vNodeToTime[next], m_iTime);
234.                         }
235.                 }
236.                 if (iRegionCount < 2)
237.                 {
238.                         m_vCutNewRegion[cur].clear();
239.                 }
240.                 return iMinTime;
241.         }
242.         const int m_iSize;
243.         const vector<int>& Time()const { return m_vNodeToTime; }//各节点的时间戳
244.         const vector<int>& RegionFirstTime()const { return m_vRegionFirstTime; }//各连通区域的最小时间戳
245.         vector<bool> Cut()const {
246.                 vector<bool> ret;
247.                 for (int i = 0; i < m_iSize; i++)
248.                 {
249.                         ret.emplace_back(m_vCutNewRegion[i].size());
250.                 }
251.                 return ret; }//
252.         const vector < vector<pair<int, int>>>& NewRegion()const { return m_vCutNewRegion; };
253. protected:
254.         vector<int> m_vNodeToTime;
255.         vector<int> m_vRegionFirstTime;
256.         vector < vector<pair<int, int>>> m_vCutNewRegion; //m_vCutNewRegion[c]如果存在[left,r) 表示割掉c后，时间戳[left,r)的节点会形成新区域
257.         int m_iTime = 0;
258. };
260. class CConnectAfterCutPoint
261. {
262. public:
263.         CConnectAfterCutPoint(const vector<vector<int>>& vNeiB) :m_ct(vNeiB)
264.         {
265.                 m_vTimeToNode.resize(m_ct.m_iSize);
266.                 m_vNodeToRegion.resize(m_ct.m_iSize);
267.                 for (int iNode = 0; iNode < m_ct.m_iSize; iNode++)
268.                 {
269.                         m_vTimeToNode[m_ct.Time()[iNode]] = iNode;
270.                 }
271.                 for (int iTime = 0,iRegion= 0; iTime < m_ct.m_iSize; iTime++)
272.                 {
273.                         if ((iRegion < m_ct.RegionFirstTime().size()) && (m_ct.RegionFirstTime()[iRegion] == iTime))
274.                         {
275.                                 iRegion++;
276.                         }
277.                         m_vNodeToRegion[m_vTimeToNode[iTime]] = (iRegion - 1);
278.                 }
279.         }
280.         bool Connect(int src, int dest, int iCut)const
281.         {
282.                 if (m_vNodeToRegion[src] != m_vNodeToRegion[dest])
283.                 {
284.                         return false;//不在一个连通区域
285.                 }
286.                 if (0 == m_ct.NewRegion()[iCut].size())
287.                 {//不是割点
288.                         return true;
289.                 }
290.                 const int r1 = GetCutRegion(iCut, src);
291.                 const int r2 = GetCutRegion(iCut, dest);
292.                 return r1 == r2;
293.         }
294.         vector<vector<int>> GetSubRegionOfCut(const int iCut)const
295.         {//删除iCut及和它相连的边后，iCut所在的区域会分成几个区域：父节点一个区域、各子节点                一个区域
296.                         //父节点所在区域可能为空，如果iCut所在的连通区域只有一个节点，则返回一个没有节点的                        区域。
297.                 const auto& v = m_ct.NewRegion()[iCut];
298.                 vector<int> vParen;
299.                 const int iRegion = m_vNodeToRegion[iCut];
300.                 const int iEndTime = (iRegion + 1 == m_ct.RegionFirstTime().size()) ? m_ct.m_iSize : m_ct.RegionFirstTime()[iRegion+1];
301.                 vector<vector<int>> vRet;       
302.                 for (int iTime = m_ct.RegionFirstTime()[iRegion],j=-1; iTime < iEndTime; iTime++)
303.                 {
304.                         if (iCut == m_vTimeToNode[iTime])
305.                         {
306.                                 continue;
307.                         }
308.                         if ((j + 1 < v.size()) && (v[j + 1].first == iTime))
309.                         {
310.                                 j++;
311.                                 vRet.emplace_back();
312.                         }
313.                         const int iNode = m_vTimeToNode[iTime];
314.                         if ((-1 != j ) && (iTime >= v[j].first) && (iTime < v[j].second))
315.                         {
316.                                 vRet.back().emplace_back(iNode);
317.                         }
318.                         else
319.                         {
320.                                 vParen.emplace_back(iNode);
321.                         }                       
322.                 }
323.                 vRet.emplace_back();
324.                 vRet.back().swap(vParen);
325.                 return vRet;
326.         }       
327. protected:
328.         int GetCutRegion(int iCut, int iNode)const
329.         {
330.                 const auto& v = m_ct.NewRegion()[iCut];
331.                 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; });
332.                 if (v.begin() == it)
333.                 {
334.                         return v.size();
335.                 }
336.                 --it;
337.                 return (it->second > m_ct.Time()[iNode]) ? (it - v.begin()) : v.size();
338.         }
339.         vector<int> m_vTimeToNode;
340.         vector<int> m_vNodeToRegion;//各节点所在区域
341.         const CCutPoint m_ct;
342. };
344. class Solution {
345. public:
346.         vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
347.                 m_c = edges.size() + 1;
348.                 m_vDisToRoot.resize(m_c);
349.                 m_vParent.resize(m_c);
350.                 m_vLeve.resize(m_c);
351.                 auto neiBo = CNeiBo::Three(m_c, edges, false, 0);
352.                 DFS(neiBo, 0, -1, 0, 0);
353.                 C2Parents par(m_vParent, m_vLeve);
354.                 auto neiBo2 = CNeiBo::Two(m_c, edges, false, 0);
355.                 CConnectAfterCutPoint cut(neiBo2);
356.                 vector<int> vRet(m_c);
357.                 for (int c = 0; c < m_c; c++)
358.                 {
359.                         auto regs = cut.GetSubRegionOfCut(c);
360.                         int left = 0;
361.                         int& iRet = vRet[c];
362.                         for (const auto& subRegion : regs)
363.                         {
364.                                 int cur = 0;
365.                                 for (const auto& ab : subRegion)
366.                                 {
367.                                         const int pub = par.GetPublicParent(ab, c);
368.                                         const int len = m_vDisToRoot[ab] + m_vDisToRoot[c] - 2 * m_vDisToRoot[pub];
369.                                         if (0 != len % signalSpeed)
370.                                         {
371.                                                 continue;
372.                                         }
373.                                         cur++;
374.                                 }
375.                                 iRet += left * cur;
376.                                 left += cur;
377.                         }
378.                 }
379.                 return vRet;
380.         }
381.         void DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par, int leve, int dis)
382.         {
383.                 m_vDisToRoot[cur] = dis;
384.                 m_vParent[cur] = par;
385.                 m_vLeve[cur] = leve;
386.                 for (const auto& [next, len] : neiBo[cur])
387.                 {
388.                         if (next == par)
389.                         {
390.                                 continue;
391.                         }
392.                         DFS(neiBo, next, cur, leve + 1, dis + len);
393.                 }
394.         }
395.         vector<int> m_vDisToRoot, m_vParent, m_vLeve;
396.         int m_c;
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++**实现。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。