Description

给出一棵树， 个查询，每次查询给出 代表病毒在 点爆发，在 的温度可以传播
根节点为 ，保证离根节点越近，温度越高，根节点温度最高。

Solution

我们知道，对于一个初始节点，它的子树必定温度小于它本身，所以设当前温度为 , 中 的这一部分可以直接查询子树里有多少符合的，但是 的在祖先上，无法解决。显然保证离根节点越近，温度越高，根节点温度最高。对于解决问题具有重大的意义，这说明我们可以树上倍增跳到最高可行的祖先（满足 ），然后直接用划分树查询子树，查询子树需要懂得如何将子树关系用 序转换成区间。
树上倍增的做法模仿了倍增求LCA，划分树是复制 的模板，最后跑的还挺快的。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48559738