倍增 0pts 求助

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include<bits/stdc++.h>
#define int long long
#define endl '\n'
// #define MSOD

using namespace std;
using ll = long long;

constexpr ll N = 3e5 + 5, INF = 5e18;

bool ST;
int n, m;
ll sm[N], ct[N], fa[N][20];
ll h[N], nd[N][20], mul[N][20], add[N][20];
bool ED;
inline void solve()	{
	cin>>n>>m;
	for(int i = 0 ; i < N ; i ++) {
		fill(nd[i], nd[i] + 20, INF);
	}
	for(int i = 1 ; i <= n ; i ++) {
		cin>>h[i];
	}
	for(int i = 0 ; i < N ; i ++) {
		fill(mul[i], mul[i] + 20, 1);
	}
	for(int i = 2 ; i <= n ; i ++) {
		int a;
		ll v;
		cin>>fa[i][0]>>a>>v;
		if(a == 0) {mul[i][0] = 1, add[i][0] = v;}
		else {mul[i][0] = v, add[i][0] = 0;}
	}
	for(int i = 2 ; i <= n ; i ++) {
		nd[i][0] = max(h[i], (max(0ll, h[fa[i][0]] - add[i][0]) + mul[i][0] - 1) / mul[i][0]);
		add[i][0] += add[fa[i][0]][0];
		mul[i][0] *= mul[fa[i][0]][0];
	}
	for(int i = 1 ; i <= 19 ; i ++) {
		for(int j = 1 ; j <= n ; j ++) {
			fa[j][i] = fa[fa[j][i - 1]][i - 1];
			if(fa[j][i]) {
				mul[j][i] = mul[j][i - 1] * mul[fa[j][i - 1]][i - 1];
				add[j][i] = mul[fa[j][i - 1]][i - 1] * add[j][i - 1] + add[fa[j][i - 1]][i - 1];
				if(mul[j][i - 1] == 0) {
					nd[j][i] = max(nd[j][i - 1], 0ll);
				} else {
					nd[j][i] = max(nd[j][i - 1], (nd[fa[j][i - 1]][i - 1] - add[j][i - 1] + mul[j][i - 1] - 1) / (mul[j][i - 1]));
				}
			}
		}
	}
	for(int i = 1 ; i <= m ; i ++) {
		int c;
		ll s;
		cin>>s>>c;
		if(s < h[c]) {ct[c] ++;continue;}
		sm[i] = 1;
		for(int j = 19 ; j >= 0 ; j --) {
			if(fa[c][j] && s >= nd[c][j]) {
				s = s * mul[c][j] + add[c][j];
				c = fa[c][j], sm[i] += (1ll << j);
			}
		}
		ct[fa[c][0]] ++;
	}
	for(int i = 1 ; i <= n ; i ++) {
		cout<<ct[i]<<endl;
	}
	for(int i = 1 ; i <= m ; i ++) {
		cout<<sm[i]<<endl;
	}
	return;
}

signed main() {
	ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
	int TC = 1;
#ifdef MSOD
	cin>>TC;
#endif
	while(TC --) {
		solve();
	}
	return 0;
}