题目描述
不远的一年前，小V还是一名清华集训的选手，坐在机房里为他已如风中残烛的OI生涯做最后的挣扎。而如今，他已成为了一名光荣的出题人。他感到非常激动，不禁感叹道：“Hello world!”。
小V有$n$道题，他的题都非常毒瘤，所以关爱选手的ufozgg打算削弱这些题。为了逃避削弱，小V把他的毒瘤题都藏到了一棵$n$个节点的树里（节点编号从$1$至$n$），这棵树上的所有节点与小V的所有题一一对应。小V的每一道题都有一个毒瘤值，节点 $i$ （表示标号为 $i$ 的树上节点，下同）对应的题的毒瘤值为 $a_i$ 。
魔法师小V为了保护他的题目，对这棵树施了魔法，这样一来，任何人想要一探这棵树的究竟，都必须在上面做跳跃操作。每一次跳跃操作包含一个起点 $s$ 、一个终点 $t$ 和一个步频 $k$ ，这表示跳跃者会从 $s$ 出发，在树上沿着简单路径多次跳跃到达 $t$ ，每次跳跃，如果从当前点到 $t$ 的最短路长度不超过 $k$ ，那么跳跃者就会直接跳到 $t$ ，否则跳跃者就会沿着最短路跳过恰好 $k$ 条边。
既然小V把题藏在了树里，ufozgg就不能直接削弱题目了。他就必须在树上跳跃，边跳跃边削弱题目。ufozgg每次跳跃经过一个节点（包括起点 $s$ ，当 $s=t$ 的时候也是如此），就会把该节点上的题目的毒瘤值开根并向下取整：即如果他经过了节点$i$，他就会使$a_i=lfloor{sqrt{a_i}}rfloor$。这种操作我们称为削弱操作。
ufozgg还会不时地希望知道他对题目的削弱程度。因此，他在一些跳跃操作中会放弃对题目的削弱，转而统计该次跳跃经过节点的题目毒瘤值总和。这种操作我们称为统计操作。
吃瓜群众绿绿对小V的毒瘤题和ufozgg的削弱计划常感兴趣。他现在想知道ufozgg每次做统计操作时得到的结果。你能帮帮他吗？
输入格式
输入的第一行一个正整数 $n$ ，表示树的节点数。
接下来一行 $n$ 个用空格隔开的正整数 $a_1,a_2,dots,a_n$ ，依次描述每个节点上题目的毒瘤值。
接下来 $n-1$ 行，描述这棵树。每行 $2$ 个正整数 $u,v$ ，描述一条树上的边 $left( u,vright)$ 。（保证 $1leq u,vleq n$ ，保证这 $n-1$ 条边构成了一棵树）
接下来一行一个正整数 $Q$ ，表示ufozgg的操作总数。
接下来 $Q$ 行按ufozgg执行操作的先后顺序依次描述每个操作，每行 $4$ 个用空格隔开的整数 $op,s,t,k$ ，表示ufozgg此次跳跃的起点为 $s$ ，终点为 $t$ ，步频为 $k$ 。如果 $op=0$ ，表示这是一次削弱操作；如果 $op=1$ ，表示这是一次统计操作。
输出格式
对于每个统计操作，输出一行一个整数，表示此次统计操作统计到的所有题的毒瘤值总和。
数据范围与提示
对于$100%$的数据，保证$nleq 50000$，$Qleq 400000$，$1leq a_ileq {10}^{13}$，对于所有的操作保证$0leq opleq 1$，$1leq s,t,kleq n$。
这题真是劲啊。数据结构蒟蒻通过抄代码学到了好多新姿势
首先容易发现：
1.一个位置上有用的开根号操作只有$O(logloga)$次。
2.跳$k$步不好直接上数据结构维护，结合数据范围应该考虑分块。
事实上这两点都是优化的突破口。
考虑暴力怎么做：如果本次操作每次跳$k$步，那么至多将进行约$frac{n}{k}$次运算。很自然地想到以某个数$s$为界限，大于它就暴力搞，否则就采用一些技巧优化。
下面考虑$k$不超过$s$时怎么搞：
对于每一个$kleq s$建一棵树。第$k$棵树上$i$的父亲给为原树上它的第$k$个祖先。询问某个$k$时就找到第$k$棵树。
首先想要优化肯定只能靠“一个位置上有用的开根号操作只有$O(logloga)$次”的性质。因为没有什么好办法，在新树上还是只有暴力上跳，考虑利用这个性质让暴力跳的次数受到控制。
由于当某个节点的值变成1之后，再对它进行开根操作就失去了意义，所以当某个节点的权值为1时，在新树上就可以“缩掉”这个点，这个可以用并查集实现。
解决了修改操作，考虑如何高效地求和，显然考虑数据结构。直接的想法是在新树上树链剖分套树状数组，支持单点修改和区间求和。这样做会使一次复杂度为$O(log^2n)$。然后就发现学傻了：每个点维护一下它到根节点路径上的权值之和，求一条路径的权值之和的时候用两端的值加起来减去2倍$lca$的值就好了，这个用$dfs$序+树状数组可以做到$O(logn)$。
剩下的就是细节了。注意这里的$a$很大，直接调用sqrt有可能出现精度不够的情况。
块的大小好像给小一点比较好？
1 |
|
近期评论