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

一些比赛的题解 文章被收录于专栏

一些比赛的题解

全部评论

相关推荐

01-15 13:52
已编辑
河南大学 Java
六年要多久:标准头像,不吃香菜😂
点赞 评论 收藏
分享
评论
6
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务