【深度优先】【树上倍增 】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。

相关文章

MyBatis分页查询实战案例完整流程

MyBatis分页查询实战案例完整流程

《MyBatis分页查询实战案例完整流程》MyBatis是一个强大的Java持久层框架,支持自定义SQL和高级映射,本案例以员工工资信息管理为例,详细讲解如何在IDEA中使用MyBatis结合Page... 目录1. MyBATis框架简介2. 分页查询原理与应用场景2.1 分页查询的基本原理2.1.1 分
阅读更多...
深度解析Python中递归下降解析器的原理与实现

深度解析Python中递归下降解析器的原理与实现

《深度解析Python中递归下降解析器的原理与实现》在编译器设计、配置文件处理和数据转换领域,递归下降解析器是最常用且最直观的解析技术,本文将详细介绍递归下降解析器的原理与实现,感兴趣的小伙伴可以跟随... 目录引言：解析器的核心价值一、递归下降解析器基础1.1 核心概念解析1.2 基本架构二、简单算术表达
阅读更多...
深度解析Java @Serial 注解及常见错误案例

深度解析Java @Serial 注解及常见错误案例

《深度解析Java@Serial注解及常见错误案例》Java14引入@Serial注解,用于编译时校验序列化成员,替代传统方式解决运行时错误,适用于Serializable类的方法/字段,需注意签... 目录Java @Serial 注解深度解析1. 注解本质2. 核心作用(1) 主要用途(2) 适用位置3
阅读更多...
Java MCP 的鉴权深度解析

Java MCP 的鉴权深度解析

《JavaMCP的鉴权深度解析》文章介绍JavaMCP鉴权的实现方式,指出客户端可通过queryString、header或env传递鉴权信息,服务器端支持工具单独鉴权、过滤器集中鉴权及启动时鉴权... 目录一、MCP Client 侧（负责传递，比较简单）（1）常见的 mcpServers json 配置
阅读更多...
Maven中生命周期深度解析与实战指南

Maven中生命周期深度解析与实战指南

《Maven中生命周期深度解析与实战指南》这篇文章主要为大家详细介绍了Maven生命周期实战指南,包含核心概念、阶段详解、SpringBoot特化场景及企业级实践建议,希望对大家有一定的帮助... 目录一、Maven 生命周期哲学二、default生命周期核心阶段详解（高频使用）三、clean生命周期核心阶
阅读更多...
Java实现复杂查询优化的7个技巧小结

Java实现复杂查询优化的7个技巧小结

《Java实现复杂查询优化的7个技巧小结》在Java项目中,复杂查询是开发者面临的“硬骨头”,本文将通过7个实战技巧,结合代码示例和性能对比,手把手教你如何让复杂查询变得优雅,大家可以根据需求进行选择... 目录一、复杂查询的痛点：为何你的代码“又臭又长”1.1冗余变量与中间状态1.2重复查询与性能陷阱1.
阅读更多...
深度剖析SpringBoot日志性能提升的原因与解决

深度剖析SpringBoot日志性能提升的原因与解决

《深度剖析SpringBoot日志性能提升的原因与解决》日志记录本该是辅助工具,却为何成了性能瓶颈,SpringBoot如何用代码彻底破解日志导致的高延迟问题,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言第一章：日志性能陷阱的底层原理1.1 日志级别的“双刃剑”效应1.2 同步日志的“吞吐量杀手”
阅读更多...
MySQL中查询和展示LONGBLOB类型数据的技巧总结

MySQL中查询和展示LONGBLOB类型数据的技巧总结

《MySQL中查询和展示LONGBLOB类型数据的技巧总结》在MySQL中LONGBLOB是一种二进制大对象（BLOB）数据类型,用于存储大量的二进制数据,：本文主要介绍MySQL中查询和展示LO... 目录前言1. 查询 LONGBLOB 数据的大小2. 查询并展示 LONGBLOB 数据2.1 转换为十
阅读更多...
使用SpringBoot+InfluxDB实现高效数据存储与查询

使用SpringBoot+InfluxDB实现高效数据存储与查询

《使用SpringBoot+InfluxDB实现高效数据存储与查询》InfluxDB是一个开源的时间序列数据库,特别适合处理带有时间戳的监控数据、指标数据等,下面详细介绍如何在SpringBoot项目... 目录1、项目介绍2、 InfluxDB 介绍3、Spring Boot 配置 InfluxDB4、I
阅读更多...
深度解析Python yfinance的核心功能和高级用法

深度解析Python yfinance的核心功能和高级用法

《深度解析Pythonyfinance的核心功能和高级用法》yfinance是一个功能强大且易于使用的Python库,用于从YahooFinance获取金融数据,本教程将深入探讨yfinance的核... 目录yfinance 深度解析教程 (python)1. 简介与安装1.1 什么是 yfinance?
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2