【图论】【状态压缩】【树】【深度优先搜索】1617. 统计子树中城市之间最大距离

作者推荐

【动���规划】【字符串】【行程码】1531. 压缩字符串

本文涉及的知识点

图论 深度优先搜索 状态压缩 树

LeetCode1617. 统计子树中城市之间最大距离

给你 n 个城市，编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges ，其中 edges[i] = [ui, vi] 表示城市 ui 和 vi 之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 树 。

一棵 子树 是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。

对于 d 从 1 到 n-1 ，请你找到城市间 最大距离 恰好为 d 的所有子树数目。

请你返回一个大小为 n-1 的数组，其中第 d 个元素（下标从 1 开始）是城市间 最大距离 恰好等于 d 的子树数目。

请注意，两个城市间距离定义为它们之间需要经过的边的数目。

示例 1：

输入：n = 4, edges = [[1,2],[2,3],[2,4]]

输出：[3,4,0]

解释：

子树 {1,2}, {2,3} 和 {2,4} 最大距离都是 1 。

子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距离都为 2 。

不存在城市间最大距离为 3 的子树。

示例 2：

输入：n = 2, edges = [[1,2]]

输出：[1]

示例 3：

输入：n = 3, edges = [[1,2],[2,3]]

输出：[2,1]

提示：

2 public:CNeiBo2(int n, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase){m_vNeiB.resize(n);}CNeiBo2(int n, vectorm_vNeiB.resize(n);for (const auto& v : edges){m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase);if (!bDirect){m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase);}}}inline void Add(int iNode1, int iNode2){iNode1 -= m_iBase;iNode2 -= m_iBase;m_vNeiB[iNode1].emplace_back(iNode2);if (!m_bDirect){m_vNeiB[iNode2].emplace_back(iNode1);}}const int m_iN;const bool m_bDirect;const int m_iBase;vectorpublic:vectorm_vDis1.resize((1 const int inx = m_vDis2[i] - 2;if (inx = 0){vRet[inx]++;}}return vRet;}vectorvectorif (next == par){continue;}auto child = DFS(neiBo, next, cur);const int iLeftCount = statu.size();for(const auto& mask : child ){{//处理独子树const int mask1 = mask | curMask;m_vDis1[mask1] = m_vDis1[mask] + 1;m_vDis2[mask1] = max(m_vDis1[mask1], m_vDis2[mask]);statu.emplace_back(mask1);}{//非独子树for (int i = iLeftCount - 1; i = 0; i--){const int mask1 = mask | statu[i];m_vDis1[mask1] = max(m_vDis1[statu[i]], m_vDis1[mask] + 1);m_vDis2[mask1] = max(m_vDis2[statu[i]], m_vDis2[mask]);m_vDis2[mask1] = max(m_vDis2[mask1], m_vDis1[statu[i]]+ m_vDis1[mask]);statu.emplace_back(mask1);}}}}return statu;}vectorassert(t1 == t2);}templateif (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i