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

class CNeiBo
{
public: 
  static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
  {
    vector<vector<int>>  vNeiBo(n);
    for (const auto& v : edges)
    {
      vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
      if (!bDirect)
      {
        vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
      }
    }
    return vNeiBo;
  } 
  static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
  {
    vector<vector<std::pair<int, int>>> vNeiBo(n);
    for (const auto& v : edges)
    {
      vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
      if (!bDirect)
      {
        vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
      }
    }
    return vNeiBo;
  }
};
class Solution {
public:
  vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
    m_c = edges.size() + 1;
    m_iSignalSpeed = signalSpeed;   
    auto neiBo = CNeiBo::Three(m_c, edges, false, 0);   
    vector<int> vRet(m_c);
    for (int c = 0; c < m_c; c++)
    {
      int& iRet = vRet[c];
      int left = 0;
      for (const auto& [next, len] : neiBo[c])
      {
        int cur = DFS(neiBo, next, c, len);
        iRet += left * cur;
        left += cur;
      }
    }
    return vRet;
  }
  int DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par,int dis)
  {
    int iRet = (0 ==dis % m_iSignalSpeed);
    for (const auto& [next,len] : neiBo[cur])
    {
      if (next == par)
      {
        continue;
      }
      iRet +=DFS(neiBo, next, cur,dis+len);
    }
    return iRet;
  }
  int m_iSignalSpeed;
  int m_c;
};

class CNeiBo
{
public: 
  static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
  {
    vector<vector<int>>  vNeiBo(n);
    for (const auto& v : edges)
    {
      vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
      if (!bDirect)
      {
        vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
      }
    }
    return vNeiBo;
  } 
  static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
  {
    vector<vector<std::pair<int, int>>> vNeiBo(n);
    for (const auto& v : edges)
    {
      vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
      if (!bDirect)
      {
        vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
      }
    }
    return vNeiBo;
  }
};
class CUnionFind
{
public:
  CUnionFind(int iSize) :m_vNodeToRegion(iSize)
  {
    for (int i = 0; i < iSize; i++)
    {
      m_vNodeToRegion[i] = i;
    }
    m_iConnetRegionCount = iSize;
  } 
  CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
  {
    for (int i = 0; i < vNeiBo.size(); i++) {
      for (const auto& n : vNeiBo[i]) {
        Union(i, n);
      }
    }
  }
  int GetConnectRegionIndex(int iNode)
  {
    int& iConnectNO = m_vNodeToRegion[iNode];
    if (iNode == iConnectNO)
    {
      return iNode;
    }
    return iConnectNO = GetConnectRegionIndex(iConnectNO);
  }
  void Union(int iNode1, int iNode2)
  {
    const int iConnectNO1 = GetConnectRegionIndex(iNode1);
    const int iConnectNO2 = GetConnectRegionIndex(iNode2);
    if (iConnectNO1 == iConnectNO2)
    {
      return;
    }
    m_iConnetRegionCount--;
    if (iConnectNO1 > iConnectNO2)
    {
      UnionConnect(iConnectNO1, iConnectNO2);
    }
    else
    {
      UnionConnect(iConnectNO2, iConnectNO1);
    }
  }
  bool IsConnect(int iNode1, int iNode2)
  {
    return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
  }
  int GetConnetRegionCount()const
  {
    return m_iConnetRegionCount;
  }
  vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
  {
    const int iNodeSize = m_vNodeToRegion.size();
    vector<int> vRet(iNodeSize);
    for (int i = 0; i < iNodeSize; i++)
    {
      vRet[GetConnectRegionIndex(i)]++;
    }
    return vRet;
  }
  std::unordered_map<int, vector<int>> GetNodeOfRegion()
  {
    std::unordered_map<int, vector<int>> ret;
    const int iNodeSize = m_vNodeToRegion.size();
    for (int i = 0; i < iNodeSize; i++)
    {
      ret[GetConnectRegionIndex(i)].emplace_back(i);
    }
    return ret;
  }
private:
  void UnionConnect(int iFrom, int iTo)
  {
    m_vNodeToRegion[iFrom] = iTo;
  }
  vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
  int m_iConnetRegionCount;
};
class CParents
{
public:
  CParents(vector<int>& vParent, const int iMaxLeve)
  { 
    int iBitNum = 0;
    for (; (1 << iBitNum) < iMaxLeve; iBitNum++);
    const int n = vParent.size();
    m_vParents.assign(iBitNum+1, vector<int>(n, -1));
    m_vParents[0] = vParent;
    //树上倍增
    for (int i = 1; i < m_vParents.size(); i++)
    {
      for (int j = 0; j < n; j++)
      {
        const int iPre = m_vParents[i - 1][j];
        if (-1 != iPre)
        {
          m_vParents[i][j] = m_vParents[i - 1][iPre];
        }
      }
    }
  }
  int GetParent(int iNode, int iLeve)const
  {
    int iParent = iNode;
    for (int iBit = 0; iBit < m_vParents.size(); iBit++)
    {
      if (-1 == iParent)
      {
        return iParent;
      }
      if (iLeve & (1 << iBit))
      {
        iParent = m_vParents[iBit][iParent];
      }
    }
    return iParent;
  } 
protected:
  vector<vector<int>> m_vParents;
};
class C2Parents : CParents
{
public:
  C2Parents(vector<int>& vParent, const vector<int>& vLeve) :m_vLeve(vLeve)
    , CParents(vParent,*std::max_element(vLeve.begin(), vLeve.end()))
  {   
  } 
  int GetPublicParent(int iNode1, int iNode2)const
  {
    int leve0 = m_vLeve[iNode1];
    int leve1 = m_vLeve[iNode2];
    if (leve0 < leve1)
    {
      iNode2 = GetParent(iNode2, leve1 - leve0);
      leve1 = leve0;
    }
    else
    {
      iNode1 = GetParent(iNode1, leve0 - leve1);
      leve0 = leve1;
    }
    //二分查找
    int left = -1, r = leve0;
    while (r - left > 1)
    {
      const auto mid = left + (r - left) / 2;
      const int iParent0 = GetParent(iNode1, mid);
      const int iParent1 = GetParent(iNode2, mid);
      if (iParent0 == iParent1)
      {
        r = mid;
      }
      else
      {
        left = mid;
      }
    }
    return GetParent(iNode1, r);
  }
protected:
  vector<vector<int>> m_vParents;
  const vector<int> m_vLeve;
};
class CCutPointEx
{
public:
  CCutPointEx(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
  {
    m_vNodeToTime.assign(m_iSize, -1);
    m_vChildFirstEnd.resize(m_iSize);
    m_vNodeToRegion.assign(m_iSize, -1);
    m_vCut.assign(m_iSize, false);
    for (int i = 0; i < m_iSize; i++)
    {
      if (-1 != m_vNodeToTime[i])
      {
        continue;
      }
      dfs(i, -1, vNeiB);
      m_iRegionCount++;
    }
    m_vTimeToNode.resize(m_iSize);
    for (int i = 0; i < m_iSize; i++)
    {
      m_vTimeToNode[m_vNodeToTime[i]] = i;;
    }
  }
  bool Visit(int src, int dest, int iCut)const
  {
    if (m_vNodeToRegion[src] != m_vNodeToRegion[dest])
    {
      return false;//不在一个连通区域
    }
    if (!m_vCut[iCut])
    {
      return true;
    }
    const int r1 = GetCutRegion(iCut, src);
    const int r2 = GetCutRegion(iCut, dest);
    return r1 == r2;
  }
  vector<vector<int>> GetSubRegionOfCut(const int iCut)const
  {//删除iCut及和它相连的边后，iCut所在的区域会分成几个区域：父节点一个区域、各子节点一个区域
   //父节点所在区域可能为空，如果iCut所在的连通区域只有一个节点，则返回一个没有节点的区域。
    const auto& v = m_vChildFirstEnd[iCut];
    vector<vector<int>> vRet(1);      
    int j = 0;
    for (int iTime=0;iTime < m_iSize; iTime++ )
    {
      const int iNode = m_vTimeToNode[iTime];
      if ((j < v.size()) && ( iTime  >= v[j].first ))
      {
        j++;
        vRet.emplace_back();
      }
      if ((iCut != iNode) && (m_vNodeToRegion[iNode] == m_vNodeToRegion[iCut]))
      {
        if (v.size()&&(iTime >= v.back().second))
        {
          vRet[0].emplace_back(iNode);
        }
        else
        {
          vRet.back().emplace_back(iNode);
        }
      }
    }
    return vRet;
  }
protected:
  int dfs(int cur, int parent, const vector<vector<int>>& vNeiB)
  {
    auto& curTime = m_vNodeToTime[cur];
    m_vNodeToRegion[cur] = m_iRegionCount;
    curTime = m_iTime++;
    int iCutChild = 0;
    int iMinTime = curTime;
    for (const auto& next : vNeiB[cur])
    {
      if (-1 != m_vNodeToTime[next])
      {
        iMinTime = min(iMinTime, m_vNodeToTime[next]);
        continue;
      }
      int iChildBeginTime = m_iTime;
      const int iChildMinTime = dfs(next, cur, vNeiB);
      iMinTime = min(iMinTime, iChildMinTime);
      if (iChildMinTime >= curTime)
      {
        iCutChild++;
        m_vChildFirstEnd[cur].push_back({ iChildBeginTime,m_iTime });
      };
    }
    m_vCut[cur] = (iCutChild + (-1 != parent)) >= 2;
    return iMinTime;
  }
  int GetCutRegion(int iCut, int iNode)const
  {
    const auto& v = m_vChildFirstEnd[iCut];
    auto it = std::upper_bound(v.begin(), v.end(), m_vNodeToTime[iNode], [](int time, const std::pair<int, int>& pr) {return time < pr.first; });
    if (v.begin() == it)
    {
      return v.size();
    }
    --it;
    return (it->second > m_vNodeToTime[iNode]) ? (it - v.begin()) : v.size();
  }
  int m_iTime = 0;
  const int m_iSize;//时间戳
  int m_iRegionCount = 0;
  vector<int> m_vNodeToTime;//各节点到达时间，从0开始。 -1表示未处理
  vector<bool> m_vCut;//是否是割点
  vector<int> m_vNodeToRegion;//各节点所在区域
  vector<vector<pair<int, int>>> m_vChildFirstEnd;//左闭右开空间[0,m_vChildFirstEnd[0].first)和[m_vChildFirstEnd.back().second,iSize)是一个区域
  vector<int> m_vTimeToNode;
};