参考代码

#include <bits/stdc++.h>
#define ld long double
#define int long long
using namespace std;
const int N = 6e5 + 10;
struct Node {
	ld x;
	int id;
	bool operator < (const Node & b) const {
		return x > b.x;
	}
};
vector<int> g[N];
priority_queue<Node> q[N];
int d[N], s[N], cnt[N], h[N], w[N], a[N], v[N], n, m;
int p[N], u[N];
ld mul[N], add[N];
void merge(int u, int v) {
	int x = s[u];
	int y = s[v];
	if (q[x].size() > q[y].size()) swap(x, y);
	while (!q[x].empty()) {
		Node t = q[x].top(); q[x].pop();
		ld val = t.x * mul[x] + add[x];
		val = (val - add[y]) / mul[y];
		q[y].push({val, t.id});
	}
	s[u] = y;
}
void dfs(int u) {
	for (int v : g[u]) {
		d[v] = d[u] + 1;
		dfs(v);
		merge(u, v);
	}
	// t * mul[s[u]] + add[s[u]] < h[u]
	int x = s[u];
	while (!q[x].empty() && q[x].top().x * mul[x] + add[x]
	< h[u]) {
		Node t = q[x].top(); q[x].pop();
		w[t.id] = u;
		cnt[u] ++;
	}
	if (a[u] == 0) add[x] += v[u];
	else mul[x] *= v[u], add[x] *= v[u];
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) 
		scanf("%lld", &h[i]);
	for (int i = 2; i <= n; ++i) {
		int f;
		scanf("%lld %lld %lld", &f, &a[i], &v[i]);
		g[f].push_back(i);
	}
	for (int i = 1; i <= n; ++i) {
		s[i] = i;
		mul[i] = 1;
		add[i] = 0;
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%lld %lld", &p[i], &u[i]);
		int x = s[u[i]];
		q[x].push({p[i], i});
	}
	d[1] = 1;
	dfs(1);
	
	for (int i = 1; i <= n; ++i)
		printf("%lld\n", cnt[i]);
	for (int i = 1; i <= m; ++i) {
		printf("%lld\n", d[u[i]] - d[w[i]]);
	}
	return 0;
}