乐观镜子

文章
8
资源
0
加入时间
2年10月17天

Alyona and a tree (树上倍增+差分)

题意: 来源(洛谷翻译题解:首先先转化一下问题,题目问当前结点(u)的子树中有多少个孩子(设为v)满足dis(u,v)<=a[v],那么我们可以统计每个结点分别对哪些结点做出了贡献。首先考虑暴力的解法,枚举每个点,针对于每一个结点,不断的去往上找他的父亲结点,并且在找的过程中给每个结点+1的权值,直到找到的结点跟当前结点的距离大于当前结点为止。这样的时间复杂度最差是n^2。我们发现一步一步的往上找,显然很暴力,对于这种题目,我们可以用类似于二分的方法去查找,那也就是倍增了,显然我