和一个长度为

大家好我是星恒今天给大家带来的是一道图里面有关公共子祖先的题目理解起来简单大家

题目leetcode

。

在一次操作中你可以选择树上的任意一条边并将其权重更改为任意值。

注意

查询之间

[[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]],

queries

[[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]],

queries

分析我们先看这道题的最直接的问题如何寻找修改最少次数我们只需要贪心的让两个点之间所有边变为边权重出现最多的次数的权重例如寻找a和b两点间修改的最小次数如果ab两点间所有边中权重2出现的次数最多我们就让所有边的值改为2这样修改的次数就最少了

好知道这一点我们的问题就变成了寻找两点间所有权重中哪个权重出现次数最多。

我们从提示中可以看出权重的取值范围为1

26我们可以计算每个点到根节点开始节点的每个权重出现的次数然后当我们计算两点之间的最小

权重出现次数

难点寻找公共祖先这个大家可以在网上了解一下这里使用Tarjan

算法推荐链接https://oi.wiki/graph/lca/#tarjan-%E7%AE%97%E6%B3%95

class

{neighbors[edge[0]].put(edge[1],

edge[2]);neighbors[edge[1]].put(edge[0],

queryArr

{queryArr[queries[i][0]].add(new

int[]{queries[i][1],

i});queryArr[queries[i][1]].add(new

int[]{queries[i][0],

{System.arraycopy(count[parent],

count[node],

1);count[node][neighbors[node].get(parent)];}uf[node]

node;for

如果大家是为了面试不需要了解这个算法如果是为了蓝桥杯建议看一下这个算法

如果大家有什么思考和问题可以在评论区讨论也可以私信我很乐意为大家效劳。

好啦今天的每日一题到这里就结束了如果大家觉得有用可以可以给我一个小小的赞呢我们下期再见