Description
小铭铭最近获得了一副新的桌游，游戏中需要用m个骑士攻占n个城池。
这n个城池用1到n的整数表示。除1号城池外，城池i会受到另一座城池fi的管辖，其中fi 每个城池有一个防御值hi，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力将发生变化，然后继续攻击管辖这座城池的城池，直到占领1号城池，或牺牲为止。
除1号城池外，每个城池i会给出一个战斗力变化参数ai，vi。若ai=0，攻占城池i以后骑士战斗力会增加vi；若ai=1，攻占城池i以后，战斗力会乘以vi。
注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。
现在的问题是，对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。
Input
第1行包含两个正整数n,m，表示城池的数量和骑士的数量。
第2行包含n个整数，其中第i个数为hi，表示城池i的防御值。
第3到n+1行，每行包含三个整数。其中第i+1行的三个数为fi,ai,vi，分别表示管辖这座城池的城池编号和两个战斗力变化参数。
第n+2到n+m+1行，每行包含两个整数。其中第n+i行的两个数为si,ci，分别表示初始战斗力和第一个攻击的城池。
Output
输出n+m行，每行包含一个非负整数。其中前n行分别表示在城池1到n牺牲的骑士数量，后m行分别表示骑士1到m攻占的城池数量。
Sample Input
5 5
50 20 10 10 30
1 1 2
2 0 5
2 0 -10
1 0 10
20 2
10 3
40 4
20 4
35 5
Sample Output
2
2
0
0
0
1
1
3
1
1
网上的很多题解都是可并堆。这里提供一种倍增的做法。
我们设表示从i开始，占领了
座城池（包括i）时，战斗力会乘以
。
表示占领了
座城池（包括i）时，战斗力会增加
。
表示占领
座城池（包括i）所需要的最小初始战斗力。
按照【AHOI2009】行星序列的维护方法倍增维护与
。代码如下：
mul[i][j]=mul[i][j-1]*mul[fa[i][j-1]][j-1];
add[i][j]=add[i][j-1]*mul[fa[i][j-1]][j-1]+add[fa[i][j-1]][j-1];然后维护的代码如下：
mn[i][j]=max(mn[i][j-1],(mn[fa[i][j-1]][j-1]-add[i][j-1]+mul[i][j-1]-1)/mul[i][j-1]);我们假设为
，在i点是战斗力为
，则
，
所以（向上取整）。
道理很简单，我们设初始战斗力为，到某个点时，战斗力乘了a，加了b，那么
,
，然后维护x的最小合法值就行了。然而naive的我考试是一直想用同样的思路维护
的最大值，然后就原地爆炸。。。
所以，我们要学会选择合适的变量维护，不要一颗树上吊死。