甜美短靴

文章
5
资源
0
加入时间
2年10月21天

B. Alyona and a tree(思维+倍增/二分+树上差分)

https://codeforces.com/problemset/problem/739/B思路:对于题目的条件,转化成对于某个点,其有多少点能控制它。朴素就是每个点网上跳对于每个点能更新的更新,不能更新意味着break。O(n^2)break意味着其条件满足单调性,于是可以树上二分能到的最远的祖先,当然了,倍增也是同样的道理,其二进制能表示出最远的祖先。然后对于起点到祖先的一段区间,我们可以直接+1,树上差分比较方便(当然你硬要写个树剖再多个log.....也无话说对于求带边权的两点