rt，正常倍增过了

事实上算一算空间是完全够用的，那么是否需要开小空间限制

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;
const int MAXN = 300010;

int n, m;
ll h[MAXN];
int dep[MAXN], fa[MAXN], lg[MAXN], anc[MAXN][19];
ll ned[MAXN][19], mul[MAXN][19], add[MAXN][19];
int ans1[MAXN], ans2[MAXN];

int main()
{
	scanf("%d%d",&n,&m);
	lg[0] = -1;
	for(int i=1;i<=n;i++)
		scanf("%lld",h+i), lg[i] = lg[i>>1]+1;
	for(int u=2,tp;u<=n;u++)
	{
		ll v;
		scanf("%d%d%lld",fa+u,&tp,&v);
		dep[u] = dep[fa[u]] + 1;
		if(tp) mul[u][0] = v;
		else add[u][0] = v, mul[u][0] = 1;
		anc[u][0] = fa[u];
		ned[u][0] = h[u];
		for(int i=1;i<=lg[dep[u]];i++)
		{
			int x = anc[u][i-1];
			if(!x || !anc[x][i-1]) break;
			anc[u][i] = anc[x][i-1];
			ll tmp = mul[u][i-1]<0 ? -1 : 1; 
			ned[u][i] = max(ned[u][i-1], (ned[x][i-1]-add[u][i-1]+mul[u][i-1]-tmp)/mul[u][i-1]);
			add[u][i] = add[u][i-1]*mul[x][i-1]+add[x][i-1];
			mul[u][i] = mul[u][i-1]*mul[x][i-1];
		}
	}
	/*
	for(int i=1;i<=n;i++)
	{
		printf("%d : \n",i);
		for(int j=0;j<=lg[dep[i]];j++)
			printf("%d %lld %lld %lld\n",anc[i][j],ned[i][j],mul[i][j],add[i][j]);
		puts("");
	}
	*/
	for(int j=1,u;j<=m;j++)
	{
		ll s;
		scanf("%lld%d",&s,&u);
		for(int i=lg[dep[u]];~i;i--)
		{
			if(anc[u][i] && s >= ned[u][i])
			{
				s = s * mul[u][i] + add[u][i];
				ans2[j] += dep[u] - dep[anc[u][i]];
				u = anc[u][i];
			}
		}
		if(u == 1 && s >= h[u]) ++ans2[j];
		else ++ans1[u];
	}
	for(int i=1;i<=n;i++)
		printf("%d\n",ans1[i]);
	for(int i=1;i<=m;i++)
		printf("%d\n",ans2[i]);
	return 0;
}