Eyjafjalla 2021牛客暑期多校E

该解法时间复杂度为O(nlognlogn)。
貌似很多大佬都用优秀的O(nlogn)就把题目解决了，这里提供一种时间复杂度并没那么优秀的解法（离线 + dsu on tree + 树状数组）。
题意：n个火山形成一棵树，1号火山为根节点，每一个火山都有权值，t[i]表示第i座火山的温度。
对于从根节点出发的链上的点，距离根节点越远，则温度越低。
q个询问：给出三元组{x, l, r}，表示从x节点开始蔓延，温度在[l, r]的节点数量是多少(包括x，若t[x]不属于[l, r]，则输出0)。
分析：既然是蔓延，那么则有两个方向：

1. 往儿子蔓延。
2. 往祖先蔓延(之后可能还会再往祖先的儿子蔓延)。

既然最后都要往儿子蔓延，那么问题可以转化为：
x往祖先方向最浅能蔓延到哪个祖先节点(假设为y，这一步可以通过倍增解决)，然后看y的子树里有几个节点的温度范围在[l, t[y]]内。
根据(距离根节点越远，温度越低)这个性质可以得到，y子树里温度范围在[l, t[y]]内的节点都是连通的。
那么原问题则转化为子树问题，而树上启发式合并则可以快速地解决子树问题。
将所有温度离散化之后，对于每个子树，用树状数组维护温度为[1--i]的节点数量有多少，对于当前子树的根节点y，
求温度为[l, t[y]]的节点数量，即为siz[y]-sum(l-1)
(siz[y]表示以y为根节点的子树节点数，sum(l-1)表示温度为[1--l-1]的节点数量，即树状数组的sum求前缀和的函数)。
此时可以解决q个询问中若干个以y为根节点的问题，离线即可。
O(nlogn)为树上启发式合并的时间复杂度，再加上树状数组则多加个logn。

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48567462