【图论】【状态压缩】【树】【深度优先搜索】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 <= 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]表示只有根节点
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/360201.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

FPGA工程师的重要技能

写代码是最难的嘛&#xff1f; 不是 会调试代码才是你的闪光点&#xff01;&#xff01; 很多人觉得写代码是最重要的但这不是一个优秀的FPGA工程师的核心竞争力 企业工作也更加注重你调试代码的能力 因此我们的课程老师对课程设计也是很有要求的 写代码是最难的嘛&#…

HT71663 13V,12A全集成同步升压转换器 中文资料 规格书

HT71663是一款高功率、全集成升压转换器&#xff0c;集成16mΩ功率开关管和23mΩ同步整流管&#xff0c;为便携式系统提供G效的小尺寸处理方案。 HT71663具有2.7V至13V宽输入电压范围&#xff0c;可为采用单节或两节锂电池的应用提供支持。该器件具备10A开关电流能力&#xff…

CHS_05.2.3.4_1+信号量机制

CHS_05.2.3.4_1信号量机制 知识总览信号量机制信号量机制——整型信号量信号量机制——记录型信号量知识回顾 在这个小节中 我们会学习信号量 机制这个极其重要的知识点 知识总览 在考研当中 我们需要掌握两种类型的信号量 一种是整形信号量 另一种是记录型信号量 我们会在后面…

数字孪生模型优化平台

老子云模型优化服务平台 一、模型优化 使用单模型轻量化、格式转换、倾斜摄影轻量化服务。 1、格式转换 只需上传原始单模型文件&#xff0c;就能在云端自动发起转换。 服务介绍&#xff1a; 支持格式输出为FBX、OBJ、STL、STP格式&#xff08;其他输出格式陆续上线中&…

企业级大数据安全架构(七)服务安全

作者&#xff1a;楼高 在企业级大数据安全方案中&#xff0c;本节主要介绍服务安全问题&#xff0c;引入kerberos认证机制&#xff0c;目前直接对接kerberos使用较多&#xff0c;这里我们使用FreeIPA来集成kerberos FreeIPA官网下载地址&#xff1a;https://www.freeipa.org/p…

Android systemui 编译

目录 简介&#xff1a; 一、步骤 二、下载源码 三、环境配置 四、确定好需要编译版本 五、编译SystemUI 步骤1&#xff1a;进入源代码目录 步骤2&#xff1a;初始化编译环境 步骤3&#xff1a;选择目标设备 步骤4&#xff1a;编译SystemUI 步骤5&#xff1a;查找生成…

指针的深入了解6

1.回调函数 回调函数就是一个通过函数指针调用的函数。 如果你把函数的指针&#xff08;地址&#xff09;作为参数传递给另一个函数&#xff0c;当这个指针被用来调用其所指向的函数 时&#xff0c;被调用的函数就是回调函数。回调函数不是由该函数的实现方直接调用&#xff0…

【Tomcat与网络5】再论Tomcat的工作过程与两种经典的设计模式

前面两篇&#xff0c;我们重点分析了Tomcat的容器和连接器的基本设计&#xff0c;今天我们来看一下两个机构如何在service的调度下进行协同工作的。 目录 1.模板模式与Tomcat的重用性设计 2.观察者模式与Tomcat可扩展性设计 1.模板模式与Tomcat的重用性设计 首先&#xff0…

车规级高压LDO正式上线

随着汽车电子行业向着智能化、物联网化的趋势发展&#xff0c;LDO的性能在车载电源设计中变得越来越重要。由于车载应用使用电池供电&#xff0c;所以对系统待机功耗有较高要求。例如感应雨刷、感应后备箱、自动大灯等功能&#xff0c;在触发前都需要保持低功耗工作&#xff0c…

Pandas.DataFrame.quantile() 分位数 详解 含代码 含测试数据集 随Pandas版本持续更新

关于Pandas版本&#xff1a; 本文基于 pandas2.2.0 编写。 关于本文内容更新&#xff1a; 随着pandas的stable版本更迭&#xff0c;本文持续更新&#xff0c;不断完善补充。 传送门&#xff1a; Pandas API参考目录 传送门&#xff1a; Pandas 版本更新及新特性 传送门&…

Flask 入门2:路由

1. 前言 在上一节中&#xff0c;我们使用到了静态路由&#xff0c;即一个路由规则对应一个 URL。而在实际应用中&#xff0c;更多使用的则是动态路由&#xff0c;它的 URL是可变的。 2. 定义一个很常见的路由地址 app.route(/user/<username>) def user(username):ret…

java servlet勤工助学家教管系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 java servlet 勤工助学家教管系统是一套完善的java web信息管理系统 serlvetdaobean mvc 模式开发 &#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为TOMCAT7.0,Myecli…

streampark+flink一键整库或多表同步mysql到doris实战

streamparkflink一键整库或多表同步mysql到doris实战&#xff0c;此应用一旦推广起来&#xff0c;那么数据实时异构时&#xff0c;不仅可以减少对数据库的查询压力&#xff0c;还可以减少数据同步时的至少50%的成本&#xff0c;还可以减少30%的存储成本&#xff1b; streampar…

2024年【天津市安全员C证】新版试题及天津市安全员C证模拟考试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 天津市安全员C证新版试题是安全生产模拟考试一点通总题库中生成的一套天津市安全员C证模拟考试题&#xff0c;安全生产模拟考试一点通上天津市安全员C证作业手机同步练习。2024年【天津市安全员C证】新版试题及天津市…

java基础(面试用)

一、基本语法 1. 注释有哪几种形式&#xff1f; //单行注释&#xff1a;通常用于解释方法内某单行代码的作用。 //int i 0;//多行注释&#xff1a;通常用于解释一段代码的作用。 //int i 0; //int i 0;//文档注释&#xff1a;通常用于生成 Java 开发文档。 /* *int i 0; …

实现自己的小功能(方案二)

第一套方案废弃的原因是数据不准确&#xff0c;大家可以使用Tushare试试&#xff0c;多测试一些。 方案二的整体流程&#xff1a; 先随机检测数据&#xff08;50条&#xff09;处理后数据的精度问题&#xff08;第一套方案也遇到了这个问题&#xff09; 1、下载数据 使用通达…

马哈鱼SQLFlow Lite的python版本

Gudu SQLFlow 是一款用来分析各种数据库的 SQL 语句和存储过程来获取复杂的数据血缘关系并进行可视化的工具。 Gudu SQLFlow Lite version for python 可以让 python 开发者把数据血缘分析和可视化能力快速集成到他们自己的 python 应用中。 Gudu SQLFlow Lite version for p…

【JAVA】Semaphore 有什么作用

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;JAVA ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 1. 二进制信号量&#xff1a; 2. 计数信号量&#xff1a; 结语 我的其他博客 前言 Semaphore&#xff08;信号量&#xff09;作为…

图扑 HT UI 5.0 全新升级,开箱即用!

为顺应数字时代的不断发展&#xff0c;图扑 HT UI 5.0 在原有功能强大的界面组件库的基础上进行了全面升级&#xff0c;融入了更先进的技术、创新的设计理念以及更加智能的功能。HT UI 5.0 使用户体验更为直观、个性化&#xff0c;并在性能、稳定性和安全性等方面达到新的高度。…

品牌时代:应对非对称性风险的战略与实践

市场环境中&#xff0c;非对称性风险成为企业必须直面的挑战。非对称性风险指的是企业在经营过程中面临的不确定性因素&#xff0c;这些因素可能导致企业遭受重大损失或获得巨大收益。为了应对这种风险&#xff0c;企业需要从产品导向转向品牌导向&#xff0c;通过品牌建设来提…