2021牛客暑期多校训练营9 E. Eyjafjalla (划分树,树上倍增)
Eyjafjalla
https://ac.nowcoder.com/acm/contest/11260/E
Description
给出一棵树, 个查询,每次查询给出
代表病毒在
点爆发,在
的温度可以传播
根节点为 ,保证离根节点越近,温度越高,根节点温度最高。
Solution
我们知道,对于一个初始节点,它的子树必定温度小于它本身,所以设当前温度为 ,
中
的这一部分可以直接查询子树里有多少符合的,但是
的在祖先上,无法解决。显然保证离根节点越近,温度越高,根节点温度最高。对于解决问题具有重大的意义,这说明我们可以树上倍增跳到最高可行的祖先(满足
),然后直接用划分树查询子树,查询子树需要懂得如何将子树关系用
序转换成区间。
树上倍增的做法模仿了倍增求LCA,划分树是复制 的模板,最后跑的还挺快的。
Code
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48559738
一些比赛的题解 文章被收录于专栏
一些比赛的题解