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

作者推荐

本文涉及的知识点

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

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 <= n <= 15
edges.length == n-1
edges[i].length == 2
1 <= ui, vi <= n
题目保证 (ui, vi) 所表示的边互不相同。

深度优先搜索

编号从1到n，变成0到n-1。
枚举所有可能的子树mask，如果mask & (1 << i ) 表示第i个节点在此树中。
任意节点为根都可以，比如：0。

状态表示

m_vDis1[mask]记录子树mask 以根节点为起点的最长路径经过的节点数。
m_vDis2[mask]记录子树mask 最长路径经过的节点数。
非法子树两者都为0。

子树的的转移方程

子树的某合法状态：以它为根节点的子树。
枚举各子树的状态，处理独子树。独子树为mask，根节点为root，则当前树为：mask1 = mask | ( 1 << root)。
m_vDis1[mask1] = m_vDis1[mask]+1
m_vDis2[mask1] = max(m_vDis1[mask1] ,m_vDis2[mask])
处理非独子树
vLeft 记录根节点和前i棵子树组成的所有合法字子树，如：mask1，第i棵子树的某合法状态 mask2。
两者合并后的新状态为mask3 = mask1 | mask2。
m_vDis1[mask3] = max(m_vDis1[mask1] ,m_vDis1[mask2]+1)
m_vDis2[mask3] = max(m_vDis2[mask1],m_vDis2[mask2],m_vDis1[mask1]+m_vDis1[mask2])

代码

核心代码

class CNeiBo2
{
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, vector<vector<int>>& edges, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase)
	{
		m_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;
	vector<vector<int>> m_vNeiB;
};

class Solution {
public:
	vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
		m_vDis1.resize((1 << n));
		m_vDis2.resize((1 << n));
		CNeiBo2 neibo(n, edges, false, 1);
		DFS(neibo.m_vNeiB, 0, -1);
		vector<int> vRet(n-1);
		for (int i = 0; i < (1 << n); i++)
		{
			const int inx = m_vDis2[i] - 2;
			if (inx >= 0)
			{
				vRet[inx]++;
			}
		}
		return vRet;
	}
	vector<int> DFS(vector<vector<int>>& neiBo,int cur,int par)
	{
		vector<int> statu;
		const int curMask = 1 << cur;
		statu.emplace_back(curMask);
		m_vDis1[curMask] = m_vDis2[curMask] = 1;
		for (const auto& next : neiBo[cur])
		{
			if (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;
	}
	vector<int> m_vDis1, m_vDis2;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(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]);
	}

}

int main()
{	
	int n;
	vector<vector<int>> edges;
	
	{
		Solution sln;
		n = 2, edges = { {1,2} };
		auto res = sln.countSubgraphsForEachDiameter(n, edges);
		Assert(res, vector<int>{1});
	}

	{
		Solution sln;
		n = 4, edges = { {1,2},{2,3},{2,4} };
		auto res = sln.countSubgraphsForEachDiameter(n, edges);
		Assert(res, vector<int>{3, 4, 0});
	}

	{
		Solution sln;
		n = 3, edges = { {1,2},{2,3} };
		auto res = sln.countSubgraphsForEachDiameter(n, edges);
		Assert(res, vector<int>{2,1});
	}
	
}

2023年2月

class Solution {
public:
vector countSubgraphsForEachDiameter(int n, vector<vector>& edges) {
m_n = n;
m_vNear.resize(n);
for (const auto& v : edges)
{
m_vNear[v[0] - 1].push_back(v[1] - 1);
m_vNear[v[1] - 1].push_back(v[0] - 1);
}
DFSForDelParent(0, -1);
BSFForNodeSort(0, -1);
m_vNodeLeveMaxDist.assign(n, vector< vector>(n + 1, vector(n + 1)));
for (auto it = m_vSortNode.rbegin(); it != m_vSortNode.rend(); ++it)
{
dfs(*it);
}
vector vRet;
for (int iMaxDis = 1; iMaxDis < n; iMaxDis++)
{
int iSum = 0;
for (int iNode = 0; iNode < n; iNode++)
{
for (int leve = 0; leve <= n; leve++)
{
iSum += m_vNodeLeveMaxDist[iNode][leve][iMaxDis + 1];
}
}
vRet.push_back(iSum);
}
return vRet;
}
void DFSForDelParent(int iCur, const int iParent)
{
auto& v = m_vNear[iCur];
for (auto it = v.begin(); it != v.end(); ++ it )
{
if (iParent == *it )
{
v.erase(it);
break;
}
}
for (auto it = v.begin(); it != v.end(); ++it)
{
DFSForDelParent(*it, iCur);
}
}
void BSFForNodeSort(int iCur, const int iParent)
{
m_vSortNode.push_back(iCur);
int iNotSubNode = m_vSortNode.size();
for (const auto& next : m_vNear[iCur])
{
m_vSortNode.push_back(next);
}
const int iNodeNum = m_vSortNode.size();
for (int i = iNotSubNode; i < iNodeNum; i++)
{
BSFForNodeSort(m_vSortNode[i], iCur);
}
}
void dfs(int iCur)
{
vector<vector> pre(m_n + 1, vector(m_n + 1));
pre[0+1][-1+1] = 1;
for (const auto& next : m_vNear[iCur])
{
vector<vector> dp(m_n + 1, vector(m_n + 1));
for (int iPreLeve = -1; iPreLeve < m_n; iPreLeve++)
{
for (int iPreMaxDis = -1; iPreMaxDis < m_n; iPreMaxDis++)
{
if (0 == pre[iPreLeve + 1][iPreMaxDis + 1])
{
continue;
}
for (int iLeve = -1; iLeve < m_n; iLeve++)
{
for (int iMaxDis = -1; iMaxDis < m_n; iMaxDis++)
{
if (0 == m_vNodeLeveMaxDist[next][iLeve + 1][iMaxDis + 1])
{
continue;
}
int iNewMaxDis = max(iPreMaxDis, max(iMaxDis, iLeve));
iNewMaxDis = max(iNewMaxDis, iPreLeve + iLeve+1 );
int iNewLeve = max(iPreLeve, iLeve + 1);
dp[iNewLeve + 1][iNewMaxDis + 1] += pre[iPreLeve + 1][iPreMaxDis + 1] * m_vNodeLeveMaxDist[next][iLeve + 1][iMaxDis + 1];
}
}
}
}
pre.swap(dp);
}
pre[-1 + 1][-1 + 1]++;
m_vNodeLeveMaxDist[iCur] = pre;
}
vector m_vSortNode;//根节点，一级节点，二级节点…
vector<vector> m_vNear;
vector<vector<vector>> m_vNodeLeveMaxDist;
int m_n;
};

2023年9月

class Solution {
public:
vector countSubgraphsForEachDiameter(int n, vector<vector>& edges) {
CNeiBo2 neiBo(n, edges, false, 1);
AssignVector3(m_vLeveNums,n,n,n,0);
dfs(0, -1, neiBo);
vector vRet(n - 1);
for (int Dis = 1; Dis < n; Dis++)
{
for (int node = 0; node < n; node++)
{
for (int leve = 0; leve < n; leve++)
{
vRet[Dis - 1] += m_vLeveNums[node][leve][Dis];
}
}
}
return vRet;
}
void dfs(int cur,int parent, CNeiBo2& neiBo)
{
m_vLeveNums[cur][0][0] = 1;
for (const auto& next : neiBo.m_vNeiB[cur])
{
if (next == parent)
{
continue;
}
dfs(next, cur, neiBo);
auto pre = m_vLeveNums[cur];
for (int preLeve = 0; preLeve < pre.size(); preLeve++)
{
for (int preDis = 0; preDis < pre.size(); preDis++)
{
for (int nextLeve = 0; nextLeve + 1 < pre.size(); nextLeve++)
{
for (int nextDis = 0; nextDis < pre.size(); nextDis++)
{
const int iNewLeve = max(nextLeve + 1, preLeve);
int iNewDis = max(preDis, preLeve + nextLeve + 1);
MaxSelf(&iNewDis, nextDis);
if (iNewDis >= pre.size())
{
continue;
}
m_vLeveNums[cur][iNewLeve][iNewDis] += pre[preLeve][preDis] * m_vLeveNums[next][nextLeve][nextDis];
}
}
}
}
}
}
vector<vector<vector>> m_vLeveNums;//m_vRet[cur][i][j]表示以cur为根，叶子距离cur最大距离为i,任意两个节点最大距离为j。m_vRet[cur][0][0]表示只有根节点
};

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

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

闻缺陷则喜何志丹