【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目（一）https://developer.aliyun.com/article/1478723
换根法DFS
树中删除一个节点，则各孩子各一个连通区域，除自己及后代外一个区域。如果这个节点是根，则简单得多。各孩子一个连通区域。
DSF(cur) 返回自己及子孙到当前根节点距离是signalSpeed 倍的节点数量。令当前根节点各孩子的返回值是{i1,i2,⋯ \cdots⋯,im} 。i1*i2+(i1+i2)*i3 ⋯ \cdots⋯ +(I1+i2+… \dots… + im − 1 _{m-1}m−1)*im。这样不必除以二。
a
class CNeiBo { public: static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<int>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase); } } return vNeiBo; } static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<std::pair<int, int>>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]); } } return vNeiBo; } }; class Solution { public: vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) { m_c = edges.size() + 1; m_iSignalSpeed = signalSpeed; auto neiBo = CNeiBo::Three(m_c, edges, false, 0); vector<int> vRet(m_c); for (int c = 0; c < m_c; c++) { int& iRet = vRet[c]; int left = 0; for (const auto& [next, len] : neiBo[c]) { int cur = DFS(neiBo, next, c, len); iRet += left * cur; left += cur; } } return vRet; } int DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par,int dis) { int iRet = (0 ==dis % m_iSignalSpeed); for (const auto& [next,len] : neiBo[cur]) { if (next == par) { continue; } iRet +=DFS(neiBo, next, cur,dis+len); } return iRet; } int m_iSignalSpeed; int m_c; };
割点
本解法过于复杂，除非用了提前封装好的割点扩展类，否则被使用。
class CNeiBo { public: static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<int>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase); } } return vNeiBo; } static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<std::pair<int, int>>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]); } } return vNeiBo; } }; class CUnionFind { public: CUnionFind(int iSize) :m_vNodeToRegion(iSize) { for (int i = 0; i < iSize; i++) { m_vNodeToRegion[i] = i; } m_iConnetRegionCount = iSize; } CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size()) { for (int i = 0; i < vNeiBo.size(); i++) { for (const auto& n : vNeiBo[i]) { Union(i, n); } } } int GetConnectRegionIndex(int iNode) { int& iConnectNO = m_vNodeToRegion[iNode]; if (iNode == iConnectNO) { return iNode; } return iConnectNO = GetConnectRegionIndex(iConnectNO); } void Union(int iNode1, int iNode2) { const int iConnectNO1 = GetConnectRegionIndex(iNode1); const int iConnectNO2 = GetConnectRegionIndex(iNode2); if (iConnectNO1 == iConnectNO2) { return; } m_iConnetRegionCount--; if (iConnectNO1 > iConnectNO2) { UnionConnect(iConnectNO1, iConnectNO2); } else { UnionConnect(iConnectNO2, iConnectNO1); } } bool IsConnect(int iNode1, int iNode2) { return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2); } int GetConnetRegionCount()const { return m_iConnetRegionCount; } vector<int> GetNodeCountOfRegion()//各联通区域的节点数量 { const int iNodeSize = m_vNodeToRegion.size(); vector<int> vRet(iNodeSize); for (int i = 0; i < iNodeSize; i++) { vRet[GetConnectRegionIndex(i)]++; } return vRet; } std::unordered_map<int, vector<int>> GetNodeOfRegion() { std::unordered_map<int, vector<int>> ret; const int iNodeSize = m_vNodeToRegion.size(); for (int i = 0; i < iNodeSize; i++) { ret[GetConnectRegionIndex(i)].emplace_back(i); } return ret; } private: void UnionConnect(int iFrom, int iTo) { m_vNodeToRegion[iFrom] = iTo; } vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引 int m_iConnetRegionCount; }; class CParents { public: CParents(vector<int>& vParent, const int iMaxLeve) { int iBitNum = 0; for (; (1 << iBitNum) < iMaxLeve; iBitNum++); const int n = vParent.size(); m_vParents.assign(iBitNum+1, vector<int>(n, -1)); m_vParents[0] = vParent; //树上倍增 for (int i = 1; i < m_vParents.size(); i++) { for (int j = 0; j < n; j++) { const int iPre = m_vParents[i - 1][j]; if (-1 != iPre) { m_vParents[i][j] = m_vParents[i - 1][iPre]; } } } } int GetParent(int iNode, int iLeve)const { int iParent = iNode; for (int iBit = 0; iBit < m_vParents.size(); iBit++) { if (-1 == iParent) { return iParent; } if (iLeve & (1 << iBit)) { iParent = m_vParents[iBit][iParent]; } } return iParent; } protected: vector<vector<int>> m_vParents; }; class C2Parents : CParents { public: C2Parents(vector<int>& vParent, const vector<int>& vLeve) :m_vLeve(vLeve) , CParents(vParent,*std::max_element(vLeve.begin(), vLeve.end())) { } int GetPublicParent(int iNode1, int iNode2)const { int leve0 = m_vLeve[iNode1]; int leve1 = m_vLeve[iNode2]; if (leve0 < leve1) { iNode2 = GetParent(iNode2, leve1 - leve0); leve1 = leve0; } else { iNode1 = GetParent(iNode1, leve0 - leve1); leve0 = leve1; } //二分查找 int left = -1, r = leve0; while (r - left > 1) { const auto mid = left + (r - left) / 2; const int iParent0 = GetParent(iNode1, mid); const int iParent1 = GetParent(iNode2, mid); if (iParent0 == iParent1) { r = mid; } else { left = mid; } } return GetParent(iNode1, r); } protected: vector<vector<int>> m_vParents; const vector<int> m_vLeve; }; class CCutPointEx { public: CCutPointEx(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size()) { m_vNodeToTime.assign(m_iSize, -1); m_vChildFirstEnd.resize(m_iSize); m_vNodeToRegion.assign(m_iSize, -1); m_vCut.assign(m_iSize, false); for (int i = 0; i < m_iSize; i++) { if (-1 != m_vNodeToTime[i]) { continue; } dfs(i, -1, vNeiB); m_iRegionCount++; } m_vTimeToNode.resize(m_iSize); for (int i = 0; i < m_iSize; i++) { m_vTimeToNode[m_vNodeToTime[i]] = i;; } } bool Visit(int src, int dest, int iCut)const { if (m_vNodeToRegion[src] != m_vNodeToRegion[dest]) { return false;//不在一个连通区域 } if (!m_vCut[iCut]) { return true; } const int r1 = GetCutRegion(iCut, src); const int r2 = GetCutRegion(iCut, dest); return r1 == r2; } vector<vector<int>> GetSubRegionOfCut(const int iCut)const {//删除iCut及和它相连的边后，iCut所在的区域会分成几个区域：父节点一个区域、各子节点一个区域 //父节点所在区域可能为空，如果iCut所在的连通区域只有一个节点，则返回一个没有节点的区域。 const auto& v = m_vChildFirstEnd[iCut]; vector<vector<int>> vRet(1); int j = 0; for (int iTime=0;iTime < m_iSize; iTime++ ) { const int iNode = m_vTimeToNode[iTime]; if ((j < v.size()) && ( iTime >= v[j].first )) { j++; vRet.emplace_back(); } if ((iCut != iNode) && (m_vNodeToRegion[iNode] == m_vNodeToRegion[iCut])) { if (v.size()&&(iTime >= v.back().second)) { vRet[0].emplace_back(iNode); } else { vRet.back().emplace_back(iNode); } } } return vRet; } protected: int dfs(int cur, int parent, const vector<vector<int>>& vNeiB) { auto& curTime = m_vNodeToTime[cur]; m_vNodeToRegion[cur] = m_iRegionCount; curTime = m_iTime++; int iCutChild = 0; int iMinTime = curTime; for (const auto& next : vNeiB[cur]) { if (-1 != m_vNodeToTime[next]) { iMinTime = min(iMinTime, m_vNodeToTime[next]); continue; } int iChildBeginTime = m_iTime; const int iChildMinTime = dfs(next, cur, vNeiB); iMinTime = min(iMinTime, iChildMinTime); if (iChildMinTime >= curTime) { iCutChild++; m_vChildFirstEnd[cur].push_back({ iChildBeginTime,m_iTime }); }; } m_vCut[cur] = (iCutChild + (-1 != parent)) >= 2; return iMinTime; } int GetCutRegion(int iCut, int iNode)const { const auto& v = m_vChildFirstEnd[iCut]; auto it = std::upper_bound(v.begin(), v.end(), m_vNodeToTime[iNode], [](int time, const std::pair<int, int>& pr) {return time < pr.first; }); if (v.begin() == it) { return v.size(); } --it; return (it->second > m_vNodeToTime[iNode]) ? (it - v.begin()) : v.size(); } int m_iTime = 0; const int m_iSize;//时间戳 int m_iRegionCount = 0; vector<int> m_vNodeToTime;//各节点到达时间，从0开始。 -1表示未处理 vector<bool> m_vCut;//是否是割点 vector<int> m_vNodeToRegion;//各节点所在区域 vector<vector<pair<int, int>>> m_vChildFirstEnd;//左闭右开空间[0,m_vChildFirstEnd[0].first)和[m_vChildFirstEnd.back().second,iSize)是一个区域 vector<int> m_vTimeToNode; };
【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目（三）https://developer.aliyun.com/article/1478726
