【深度优先】【树上倍增 】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;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255

测试用例

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);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

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 m_vParents;
};
class Solution {
public:
vector minOperationsQueries(int n, vector& edges, 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>>& 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 m_vNeiBo;
vector m_vLeve;
vector m_vParent;
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++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览60496 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/136971580"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！