AI 助理
备案控制台
开发者社区 人工智能 文章 正文

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

2024-04-10 42
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【深度优先】【树上倍增 】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++**实现。

文章标签：
人工智能
BI
算法
C++
测试技术
闻缺陷则喜何志丹
目录
相关文章
存在morning
|
7月前
|
存储 算法 程序员
【算法训练-回溯算法 二】【子集组合问题】子集、组合、子集II、组合总和
【算法训练-回溯算法 二】【子集组合问题】子集、组合、子集II、组合总和
存在morning
64 0
Codelinghu
|
2月前
|
决策智能
【LeetCode 50】77.组合(优化、剪枝操作)
【LeetCode 50】77.组合(优化、剪枝操作)
Codelinghu
15 2
hnrk7epeorhrk
|
6月前
|
机器学习/深度学习 存储 算法
技术笔记：LSH近似最近邻查找
技术笔记：LSH近似最近邻查找
hnrk7epeorhrk
52 0
yma16
|
7月前
|
存储 算法
图的深度优先算法
图的深度优先算法
yma16
42 0
闻缺陷则喜何志丹
|
7月前
|
机器学习/深度学习 算法 测试技术
【深度优先搜索】【树】【C++算法】2003. 每棵子树内缺失的最小基因值
【深度优先搜索】【树】【C++算法】2003. 每棵子树内缺失的最小基因值
闻缺陷则喜何志丹
50 0
闻缺陷则喜何志丹
|
7月前
|
算法 测试技术 C++
【动态规划】1301. 最大得分的路径数目
【动态规划】1301. 最大得分的路径数目
闻缺陷则喜何志丹
37 0
_长银_
|
7月前
|
搜索推荐
排序算法小结
排序算法小结
_长银_
29 0
闻缺陷则喜何志丹
|
人工智能 算法 BI
C++深度优先搜索的应用：在树上执行操作以后得到的最大分数
C++深度优先搜索的应用：在树上执行操作以后得到的最大分数
闻缺陷则喜何志丹
61 0
Trouble..
|
算法
无重复子集问题求解
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
Trouble..
77 0
阿兵云原生
|
Cloud Native 算法 Go
886. 可能的二分法：图+深度优先算法
这是 力扣上的 886. 可能的二分法，难度为 中等。
阿兵云原生
66 0