【树上倍增】【割点】【换根法】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)。

并集查找

classCNeiBo{public:static vector<vector<int>>Two(int n, vector<vector<int>>& edges,bool bDirect,int iBase =0){
        vector<vector<int>>vNeiBo(n);for(constauto& 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(constauto& 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;}};classCUnionFind{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(constauto& n : vNeiBo[i]){Union(i, n);}}}intGetConnectRegionIndex(int iNode){int& iConnectNO = m_vNodeToRegion[iNode];if(iNode == iConnectNO){return iNode;}return iConnectNO =GetConnectRegionIndex(iConnectNO);}voidUnion(int iNode1,int iNode2){constint iConnectNO1 =GetConnectRegionIndex(iNode1);constint iConnectNO2 =GetConnectRegionIndex(iNode2);if(iConnectNO1 == iConnectNO2){return;}
        m_iConnetRegionCount--;if(iConnectNO1 > iConnectNO2){UnionConnect(iConnectNO1, iConnectNO2);}else{UnionConnect(iConnectNO2, iConnectNO1);}}boolIsConnect(int iNode1,int iNode2){returnGetConnectRegionIndex(iNode1)==GetConnectRegionIndex(iNode2);}intGetConnetRegionCount()const{return m_iConnetRegionCount;}
    vector<int>GetNodeCountOfRegion()//各联通区域的节点数量{constint 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;constint iNodeSize = m_vNodeToRegion.size();for(int i =0; i < iNodeSize; i++){
            ret[GetConnectRegionIndex(i)].emplace_back(i);}return ret;}private:voidUnionConnect(int iFrom,int iTo){
        m_vNodeToRegion[iFrom]= iTo;}
    vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引int m_iConnetRegionCount;};classCParents{public:CParents(vector<int>& vParent,const vector<int>& vLeve):m_vLeve(vLeve){constint iMaxLeve =*std::max_element(vLeve.begin(), vLeve.end());int iBitNum =0;for(;(1<< iBitNum)< iMaxLeve; iBitNum++);constint 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++){constint iPre = m_vParents[i -1][j];if(-1!= iPre){
                    m_vParents[i][j]= m_vParents[i -1][iPre];}}}}intGetParent(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;}intGetPublicParent(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){constauto mid = left +(r - left)/2;constint iParent0 =GetParent(iNode1, mid);constint iParent1 =GetParent(iNode2, mid);if(iParent0 == iParent1){
                r = mid;}else{
                left = mid;}}returnGetParent(iNode1, r);}protected:
    vector<vector<int>> m_vParents;const vector<int> m_vLeve;};classSolution{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(constauto& 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;}constint pub = par.GetPublicParent(ab, c);constint len = m_vDisToRoot[ab]+ m_vDisToRoot[c]-2* m_vDisToRoot[pub];if(0!= len % signalSpeed){continue;}
                vRegionCnt[uf.GetConnectRegionIndex(ab)]++;}int&iRet = vRet[c];constint 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;}voidDFS(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(constauto&[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<classT,classT2>voidAssert(const T& t1,const T2& t2){assert(t1 == t2);}template<classT>voidAssert(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]);}}intmain(){
    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)只取一个。

classCNeiBo{public:static vector<vector<int>>Two(int n, vector<vector<int>>& edges,bool bDirect,int iBase =0){
        vector<vector<int>>vNeiBo(n);for(constauto& 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(constauto& 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;}};classSolution{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(constauto&[next, len]: neiBo[c]){int cur =DFS(neiBo, next, c, len);
                iRet += left * cur;
                left += cur;}}return vRet;}intDFS(vector<vector<std::pair<int,int>>>& neiBo,int cur,int par,int dis){int iRet =(0==dis % m_iSignalSpeed);for(constauto&[next,len]: neiBo[cur]){if(next == par){continue;}
            iRet +=DFS(neiBo, next, cur,dis+len);}return iRet;}int m_iSignalSpeed;int m_c;};

割点

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

classCNeiBo{public:static vector<vector<int>>Two(int n, vector<vector<int>>& edges,bool bDirect,int iBase =0){
        vector<vector<int>>vNeiBo(n);for(constauto& 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(constauto& 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;}};classCUnionFind{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(constauto& n : vNeiBo[i]){Union(i, n);}}}intGetConnectRegionIndex(int iNode){int& iConnectNO = m_vNodeToRegion[iNode];if(iNode == iConnectNO){return iNode;}return iConnectNO =GetConnectRegionIndex(iConnectNO);}voidUnion(int iNode1,int iNode2){constint iConnectNO1 =GetConnectRegionIndex(iNode1);constint iConnectNO2 =GetConnectRegionIndex(iNode2);if(iConnectNO1 == iConnectNO2){return;}
        m_iConnetRegionCount--;if(iConnectNO1 > iConnectNO2){UnionConnect(iConnectNO1, iConnectNO2);}else{UnionConnect(iConnectNO2, iConnectNO1);}}boolIsConnect(int iNode1,int iNode2){returnGetConnectRegionIndex(iNode1)==GetConnectRegionIndex(iNode2);}intGetConnetRegionCount()const{return m_iConnetRegionCount;}
    vector<int>GetNodeCountOfRegion()//各联通区域的节点数量{constint 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;constint iNodeSize = m_vNodeToRegion.size();for(int i =0; i < iNodeSize; i++){
            ret[GetConnectRegionIndex(i)].emplace_back(i);}return ret;}private:voidUnionConnect(int iFrom,int iTo){
        m_vNodeToRegion[iFrom]= iTo;}
    vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引int m_iConnetRegionCount;};classCParents{public:CParents(vector<int>& vParent,constint iMaxLeve){int iBitNum =0;for(;(1<< iBitNum)< iMaxLeve; iBitNum++);constint 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++){constint iPre = m_vParents[i -1][j];if(-1!= iPre){
                    m_vParents[i][j]= m_vParents[i -1][iPre];}}}}intGetParent(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;};classC2Parents:CParents{public:C2Parents(vector<int>& vParent,const vector<int>& vLeve):m_vLeve(vLeve),CParents(vParent,*std::max_element(vLeve.begin(), vLeve.end())){}intGetPublicParent(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){constauto mid = left +(r - left)/2;constint iParent0 =GetParent(iNode1, mid);constint iParent1 =GetParent(iNode2, mid);if(iParent0 == iParent1){
                r = mid;}else{
                left = mid;}}returnGetParent(iNode1, r);}protected:

    vector<vector<int>> m_vParents;const vector<int> m_vLeve;};classCCutPointEx{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;;}}boolVisit(int src,int dest,int iCut)const{if(m_vNodeToRegion[src]!= m_vNodeToRegion[dest]){returnfalse;//不在一个连通区域}if(!m_vCut[iCut]){returntrue;}constint r1 =GetCutRegion(iCut, src);constint r2 =GetCutRegion(iCut, dest);return r1 == r2;}
    vector<vector<int>>GetSubRegionOfCut(constint iCut)const{//删除iCut及和它相连的边后，iCut所在的区域会分成几个区域：父节点一个区域、各子节点一个区域//父节点所在区域可能为空，如果iCut所在的连通区域只有一个节点，则返回一个没有节点的区域。constauto& v = m_vChildFirstEnd[iCut];
        vector<vector<int>>vRet(1);int j =0;for(int iTime=0;iTime < m_iSize; iTime++){constint 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:intdfs(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(constauto& next : vNeiB[cur]){if(-1!= m_vNodeToTime[next]){
                iMinTime =min(iMinTime, m_vNodeToTime[next]);continue;}int iChildBeginTime = m_iTime;constint 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;}intGetCutRegion(int iCut,int iNode)const{constauto& 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;constint 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

测试环境

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

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

标签： c++ 树深度优先

本文转载自: https://blog.csdn.net/he_zhidan/article/details/136475121
版权归原作者 闻缺陷则喜何志丹 所有，如有侵权，请联系我们删除。