【深度优先】【树上倍增 】2846. 边权重均等查询

2024-04-06 01:12
文章标签 查询 深度 倍增 树上 优先 权重 均等 2846

本文主要是介绍【深度优先】【树上倍增 】2846. 边权重均等查询，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及知识点

深度优先 树上倍增

LeetCode2846. 边权重均等查询

现有一棵由 n 个节点组成的无向树，节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi, wi] 表示树中存在一条位于节点 ui 和节点 vi 之间、权重为 wi 的边。

另给你一个长度为 m 的二维整数数组 queries ，其中 queries[i] = [ai, bi] 。对于每条查询，请你找出使从 ai 到 bi 路径上每条边的权重相等所需的 最小操作次数 。在一次操作中，你可以选择树上的任意一条边，并将其权重更改为任意值。

注意：

查询之间 相互独立 的，这意味着每条新的查询时，树都会回到 初始状态 。
从 ai 到 bi的路径是一个由 不同 节点组成的序列，从节点 ai 开始，到节点 bi 结束，且序列中相邻的两个节点在树中共享一条边。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 条查询的答案。

示例 1：
输入：n = 7, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]], queries = [[0,3],[3,6],[2,6],[0,6]]
输出：[0,0,1,3]
在这里插入图片描述

解释：第 1 条查询，从节点 0 到节点 3 的路径中的所有边的权重都是 1 。因此，答案为 0 。
第 2 条查询，从节点 3 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 0 。
第 3 条查询，将边 [2,3] 的权重变更为 2 。在这次操作之后，从节点 2 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 1 。
第 4 条查询，将边 [0,1]、[1,2]、[2,3] 的权重变更为 2 。在这次操作之后，从节点 0 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 3 。
对于每条查询 queries[i] ，可以证明 answer[i] 是使从 ai 到 bi 的路径中的所有边的权重相等的最小操作次数。
示例 2：
在这里插入图片描述

输入：n = 8, edges = [[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]], queries = [[4,6],[0,4],[6,5],[7,4]]
输出：[1,2,2,3]
解释：第 1 条查询，将边 [1,3] 的权重变更为 6 。在这次操作之后，从节点 4 到节点 6 的路径中的所有边的权重都是 6 。因此，答案为 1 。
第 2 条查询，将边 [0,3]、[3,1] 的权重变更为 6 。在这次操作之后，从节点 0 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 2 。
第 3 条查询，将边 [1,3]、[5,2] 的权重变更为 6 。在这次操作之后，从节点 6 到节点 5 的路径中的所有边的权重都是 6 。因此，答案为 2 。
第 4 条查询，将边 [0,7]、[0,3]、[1,3] 的权重变更为 6 。在这次操作之后，从节点 7 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 3 。
对于每条查询 queries[i] ，可以证明 answer[i] 是使从 ai 到 bi 的路径中的所有边的权重相等的最小操作次数。

提示：

1 <= n <= 104
edges.length == n - 1
edges[i].length == 3
0 <= ui, vi < n
1 <= wi <= 26
生成的输入满足 edges 表示一棵有效的树
1 <= queries.length == m <= 2 * 104
queries[i].length == 2
0 <= ai, bi < n

树上倍增

先利用DFS获得树上各节点父节点和深度（我以前喜欢称为级别)，然后在次的基础上利用树上倍增求最近公共祖先。
pubtree[j] 的vSum[i][x] 记录 x和 2i-1个最近祖先 中 权重为j的数量。

代码

核心代码

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;}static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext){vector<vector<int>> vNeiBo(rCount * cCount);auto Move = [&](int preR, int preC, int r, int c){if ((r < 0) || (r >= rCount)){return;}if ((c < 0) || (c >= cCount)){return;}if (funVilidCur(preR, preC) && funVilidNext(r, c)){vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);}};for (int r = 0; r < rCount; r++){for (int c = 0; c < cCount; c++){Move(r, c, r + 1, c);Move(r, c, r - 1, c);Move(r, c, r, c + 1);Move(r, c, r, c - 1);}}return vNeiBo;}static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat){vector<vector<int>> neiBo(neiBoMat.size());for (int i = 0; i < neiBoMat.size(); i++){for (int j = i + 1; j < neiBoMat.size(); j++){if (neiBoMat[i][j]){neiBo[i].emplace_back(j);neiBo[j].emplace_back(i);}}}return neiBo;}
};class CParents
{
public:CParents(vector<int>& vParent, const int iMaxDepth){	int iBitNum = 0;for (; (1 << iBitNum) < iMaxDepth; 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 iDepth)const{int iParent = iNode;for (int iBit = 0; iBit < m_vParents.size(); iBit++){if (-1 == iParent){return iParent;}if (iDepth & (1 << iBit)){iParent = m_vParents[iBit][iParent];}}return iParent;}	
protected:vector<vector<int>> m_vParents;
};class C2Parents : public CParents
{
public:C2Parents(vector<int>& vParent, const vector<int>& vDepth) :m_vDepth(vDepth), CParents(vParent,*std::max_element(vDepth.begin(), vDepth.end())){		}	int GetPublicParent(int iNode1, int iNode2)const{int leve0 = m_vDepth[iNode1];int leve1 = m_vDepth[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_vDepth;
};class CPubSum
{
public:CPubSum(vector<int>& vQual, CParents& calPar, const int iQua,const int iMaxDepth):m_calPar(calPar){int iBitNum = 0;for (; (1 << iBitNum) < iMaxDepth; iBitNum++);m_vSum.assign(iBitNum + 1, vector<int>(vQual.size()));for (int i = 0; i < vQual.size(); i++){m_vSum[0][i] = (iQua == vQual[i]);}for (int iBit = 1; iBit < m_vSum.size(); iBit++){for (int i = 0; i < vQual.size(); i++){const int next = calPar.GetParent(i, 1 << (iBit - 1));if (-1 == next){continue;}m_vSum[iBit][i] = m_vSum[iBit - 1][i] + m_vSum[iBit - 1][next];}}}int Sum(int cur ,int cnt){int iRet = 0;for (int iBit = 0; iBit < m_vSum.size(); iBit++){if ((1 << iBit) & cnt){iRet += m_vSum[iBit][cur];cur = m_calPar.GetParent(cur, 1 << iBit);}}return iRet;}vector<vector<int>> m_vSum;CParents& m_calPar;
};
class Solution {
public:vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {m_vDepth.resize(n);m_vParent.resize(n);m_vQual.resize(n);auto vNeiBo = CNeiBo::Three(n, edges, false);	DFS(0, -1, vNeiBo, 0);C2Parents pubParent(m_vParent, m_vDepth);vector<CPubSum*> vPubSum;const int iMaxDepth = *std::max_element(m_vDepth.begin(), m_vDepth.end());for (int i = 1; i <= 26; i++){vPubSum.emplace_back(new CPubSum(m_vQual, pubParent, i, iMaxDepth));}vector<int> vRet;for (const auto& v : queries){int pub = pubParent.GetPublicParent(v[0], v[1]);	int iMin = INT_MAX;for (int i = 0; i < 26; i++){int iCnt1 = m_vDepth[v[0]] - m_vDepth[pub];int iCnt2 = m_vDepth[v[1]] - m_vDepth[pub];	const int cur = iCnt1 + iCnt2 -vPubSum[i]->Sum(v[0], iCnt1) - vPubSum[i]->Sum(v[1], iCnt2) ;iMin = min(iMin, cur);}vRet.emplace_back(iMin);}return vRet;}void DFS(int cur, int par, vector < vector<pair<int, int>>>& vNeiBo,int iQua){m_vParent[cur] = par;m_vDepth[cur] = (-1 == par) ? 0 : (m_vDepth[par] + 1);m_vQual[cur] = iQua;for (const auto& [next, qua] : vNeiBo[cur]){if (next == par){continue;}DFS(next, cur, vNeiBo, qua);}}vector<int> m_vDepth, m_vParent, m_vQual;
};

测试用例

template<class T, class T2>
void Assert(const T& t1, const T2& 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, queries;{Solution sln;n = 7, edges = { {0,1,1},{1,2,1},{2,3,1},{3,4,2},{4,5,2},{5,6,2} }, queries = { {0,3},{3,6},{2,6},{0,6} };auto res = sln.minOperationsQueries(n, edges, queries);Assert({ 0,0,1,3 }, res);}{Solution sln;n = 8, edges = { {1,2,6},{1,3,4},{2,4,6},{2,5,3},{3,6,6},{3,0,8},{7,0,2} }, queries = { {4,6},{0,4},{6,5},{7,4} };auto res = sln.minOperationsQueries(n, edges, queries);Assert({ 1,2,2,3 }, res);}
}

2023年9月版

class CParents
{
public:
CParents(int n,vector& vParent)
{
m_vParents.assign(16, vector(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)
{
int iParent = iNode;
for (int iBit = 0; iBit < 16; iBit++)
{
if (-1 == iParent)
{
return iParent;
}
if (iLeve & (1 << iBit))
{
iParent = m_vParents[iBit][iParent];
}
}
return iParent;
}
protected:
vector<vector> m_vParents;
};
class Solution {
public:
vector minOperationsQueries(int n, vector<vector>& edges, vector<vector>& queries) {
//计算各查询的公共祖先=》路径
m_vLeve.assign(n,0);
m_vParent.assign(n, -1);
vParentNums.assign(n, vector(27));
CNeiBo3 neiBo(n,edges,false,0);
DFSLeveAndParen(0, -1, 0,0, neiBo.m_vNeiB);
CParents pars(n, m_vParent);
vector vRes;
for ( int i = 0 ; i < queries.size(); i++ )
{
const auto que = queries[i];
const int iPar = GetQueParent(pars, que);
int iMax = 0;
for (int i = 1; i <= 26; i++)
{
int tmp = vParentNums[que[0]][i] + vParentNums[que[1]][i] - vParentNums[iPar][i]2;
iMax = max(iMax, tmp);
}
int iEdgeNum = m_vLeve[que[0]] + m_vLeve[que[1]]-2m_vLeve[iPar];
vRes.emplace_back(iEdgeNum - iMax);
}
return vRes;
}
int GetQueParent(CParents& pars,vector que)
{
int leve0 = m_vLeve[que[0]];
int leve1 = m_vLeve[que[1]];
if (leve0 < leve1)
{
que[1] = pars.GetParent(que[1], leve1 - leve0);
leve1 = leve0;
}
else
{
que[0] = pars.GetParent(que[0], leve0 - leve1);
leve0 = leve1;
}
//二分查找
int left = -1, r = leve0;
while (r - left > 1)
{
const auto mid = left + (r - left) / 2;
const int iParent0 = pars.GetParent(que[0], mid);
const int iParent1 = pars.GetParent(que[1], mid);
if (iParent0 == iParent1)
{
r = mid;
}
else
{
left = mid;
}
}
return pars.GetParent(que[0],r);
}
void DFSLeveAndParen(int cur, int iParent,int iW,int leve, const vector<vector<std::pair<int, int>>>& neiBo)
{
m_vParent[cur] = iParent;
m_vLeve[cur] = leve;
if (-1 != iParent)
{
vParentNums[cur] = vParentNums[iParent];
}
vParentNums[cur][iW]++;
for (const auto& [next, w] : neiBo[cur])
{
if (next == iParent)
{
continue;
}
DFSLeveAndParen(next, cur,w, leve + 1, neiBo);
}
}
vector<vector> m_vNeiBo;
vector m_vLeve;
vector m_vParent;
vector<vector> vParentNums;

};

扩展阅读

视频课程

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

这篇关于【深度优先】【树上倍增 】2846. 边权重均等查询的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/878640。

相关文章

Python 中的异步与同步深度解析(实践记录)

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步：深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步
阅读更多...
浅谈mysql的sql_mode可能会限制你的查询

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景：问题描述原因分析：解决方案：第一种：修改后，只有当前生效，若是mysql服务重启，就会失效；
阅读更多...
MySQL多列IN查询的实现

MySQL多列IN查询的实现

《MySQL多列IN查询的实现》多列IN查询是一种强大的筛选工具,它允许通过多字段组合快速过滤数据,本文主要介绍了MySQL多列IN查询的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录一、基础语法：多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析与优化1.
阅读更多...
Redis中高并发读写性能的深度解析与优化

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、
阅读更多...
最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言
阅读更多...
mybatis-plus 实现查询表名动态修改的示例代码

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu
阅读更多...
MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

《MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固通俗易懂版)》本文主要讲解了MySQL中的多表查询,包括子查询、笛卡尔积、自连接、多表查询的实现方法以及多列子查询等,通过实际例子和操... 目录复合查询1. 回顾查询基本操作group by 分组having1. 显示部门号为10的部门名，员
阅读更多...
mysql关联查询速度慢的问题及解决

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》：本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql
阅读更多...
Redis 内存淘汰策略深度解析(最新推荐)

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction（不淘汰）​2.2 ​LR
阅读更多...
mysql线上查询之前要性能调优的技巧及示例

mysql线上查询之前要性能调优的技巧及示例

《mysql线上查询之前要性能调优的技巧及示例》文章介绍了查询优化的几种方法,包括使用索引、避免不必要的列和行、有效的JOIN策略、子查询和派生表的优化、查询提示和优化器提示等,这些方法可以帮助提高数... 目录避免不必要的列和行使用有效的JOIN策略使用子查询和派生表时要小心使用查询提示和优化器提示其他常
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2