丽水品牌网站建设,商标设计图案,工作室注册流程,山西响应式网站建设价位大家好#xff0c;我是星恒#xff0c;今天给大家带来的是一道图里面有关公共子祖先的题目#xff0c;理解起来简单#xff0c;大家 题目#xff1a;leetcode 2846 现有一棵由 n 个节点组成的无向树#xff0c;节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n … 大家好我是星恒今天给大家带来的是一道图里面有关公共子祖先的题目理解起来简单大家 题目leetcode 2846 现有一棵由 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 104edges.length n - 1edges[i].length 30 ui, vi n1 wi 26生成的输入满足 edges 表示一棵有效的树1 queries.length m 2 * 104queries[i].length 20 ai, bi n
分析我们先看这道题的最直接的问题如何寻找修改最少次数我们只需要贪心的让两个点之间所有边变为边权重出现最多的次数的权重例如寻找a和b两点间修改的最小次数如果ab两点间所有边中权重2出现的次数最多我们就让所有边的值改为2这样修改的次数就最少了
好知道这一点我们的问题就变成了寻找两点间所有权重中哪个权重出现次数最多。我们从提示中可以看出权重的取值范围为1 - 26我们可以计算每个点到根节点开始节点的每个权重出现的次数然后当我们计算两点之间的最小 权重出现次数 时这样计算我们还是使用之前的例子计算a - b间count[a][i] count[b][i] - 2count[c][i]
c是公共子祖先count[a][i] 为节点a到根节点权重为i的边出现的次数
难点寻找公共祖先这个大家可以在网上了解一下这里使用Tarjan 算法推荐链接https://oi.wiki/graph/lca/#tarjan-%E7%AE%97%E6%B3%95
代码
class Solution {static final int W 26;public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {int m queries.length;MapInteger, Integer[] neighbors new Map[n];for (int i 0; i n; i) {neighbors[i] new HashMapInteger, Integer();}for (int[] edge : edges) {neighbors[edge[0]].put(edge[1], edge[2]);neighbors[edge[1]].put(edge[0], edge[2]);}Listint[][] queryArr new List[n];for (int i 0; i n; i) {queryArr[i] new ArrayListint[]();}for (int i 0; i m; i) {queryArr[queries[i][0]].add(new int[]{queries[i][1], i});queryArr[queries[i][1]].add(new int[]{queries[i][0], i});}int[][] count new int[n][W 1];boolean[] visited new boolean[n];int[] uf new int[n];int[] lca new int[m];tarjan(0, -1, neighbors, queryArr, count, visited, uf, lca);int[] res new int[m];for (int i 0; i m; i) {int totalCount 0, maxCount 0;for (int j 1; j W; j) {int t count[queries[i][0]][j] count[queries[i][1]][j] - 2 * count[lca[i]][j];maxCount Math.max(maxCount, t);totalCount t;}res[i] totalCount - maxCount;}return res;}public void tarjan(int node, int parent, MapInteger, Integer[] neighbors, Listint[][] queryArr, int[][] count, boolean[] visited, int[] uf, int[] lca) {if (parent ! -1) {System.arraycopy(count[parent], 0, count[node], 0, W 1);count[node][neighbors[node].get(parent)];}uf[node] node;for (int child : neighbors[node].keySet()) {if (child parent) {continue;}tarjan(child, node, neighbors, queryArr, count, visited, uf, lca);uf[child] node;}for (int[] pair : queryArr[node]) {int node1 pair[0], index pair[1];if (node ! node1 !visited[node1]) {continue;}lca[index] find(uf, node1);}visited[node] true;}public int find(int[] uf, int i) {if (uf[i] i) {return i;}uf[i] find(uf, uf[i]);return uf[i];}
}示例
提示很重要公共子祖先 如果大家是为了面试不需要了解这个算法如果是为了蓝桥杯建议看一下这个算法
如果大家有什么思考和问题可以在评论区讨论也可以私信我很乐意为大家效劳。好啦今天的每日一题到这里就结束了如果大家觉得有用可以可以给我一个小小的赞呢我们下期再见
