题目
https://www.luogu.com.cn/problem/P7077
这题给我好搞。不过思路精巧。
\(Solution\)
首先我们考虑一个比较简单的问题。
称函数1是加法，函数2是乘法，函数3是调用。
首先，要转换思路。原先暴力模拟，考虑函数顺序，\(O(Qn)\), 必炸。我们考虑统计每个函数对答案的贡献。这样是\(O(n)\)复杂度的。其次，我们在考虑贡献时，也不应该直接修改上去。如果对于一个函数2，这个做法瞬间就退化了。类比线段树的懒标记，我们想到，给他们打标记，最后一并计算就行了。记住一个性质：乘可以看成多次加。
我们从简单问题入手：
在不考虑函数3的情况下，对于函数2，我们自然可以维护总乘积；对于函数1，我们可以维护一个\(mul[i]\),代表当前函数被乘的次数，注意这里，这个函数被乘的次数等于后面函数的\(mul\)之积。如果前后存在多个\(f[i]\), 那么计算也是一样的。这样我们最后把每个\(a[p]\)加上\(mul[i] * v\)就可以了。
接下来考虑函数3。做法搬过来。我们变一下\(mul\)定义：调用此函数时，全局乘了多少次。也就是后面的mul不用乘了。
先把\(mul\)维护好（下面要用，否则\(sum\)维护不出）。具体来说，我们对于每一个调用函数，按照拓扑逆序递推：
我们发现，对于函数调用的函数（姑且称为子函数吧），他们的贡献没有被计算。我们这时候只维护\(mul\)是无法做的，因为子函数无法处理了，子函数会被父函数调用的次数影响。这启发我们维护\(sum[i]\)，代表\(f[i]\)被调用的次数。具体来说，我们对于每个父函数（其实就是特判,他们永远只被调用一次）
\[sum[i] = \prod \limits_{j = i + 1}^Q mul[j] \]对于每个子函数：
\[sum[u] = sum[father] * \prod \limits_{在u右边} mul[brother] \]其实就是 父函数调用多少次 乘上后面兄弟乘了多少次
到现在为止应该能理解为什么不去\(mul\)了吧。因为后面兄弟调用的次数包括父节点调用次数，不能计算啦~，乘起来答案就不对了。
不要忘记要把相同的函数加起来~
那么我们最后就可以统计答案了~
对于函数1，维护总乘数，直接乘。对于函数2，由于可能做子函数，于是我们拿\(sum\)直接\(w[p] += v * sum[i]\)。
这样就把答案统计出来了。
原来维护的mul对现在不适用了。
因为原来的mul指的是对答案的贡献次数。而现在已经求出等效的\(sum[i]\)，加上了，没必要了。mul目前的作用只有计算sum。
那么乘起来算就与sum[i]重复了。
总结：按拓扑逆序，先求单点挂着的\(mul\), 反向枚举sum[i]， 算父函数后面乘积，在拓扑正序求出sum， 最后统计答案。
标签：函数,sum,函数调用,子函数,mul,我们 From： https://www.cnblogs.com/qinyiting/p/18048781