与特殊性质A中的有关的代码详见命名空间 AA 中的内容，意味着您可以忽略掉命名空间 BB 中的内容，尽管那是有问题的。

我的思路类似于 Dijkstra 的变种，我每一次将 $b_i$ 放入优先队列 $q$ 中，接着每一次都取一个最小的 $b_i$ 进行运算。

我通过了 CCF 的样例 tree2 但是提交洛谷等 OJ 全部都挂分。经过我个人的验证，可以排除 (unsigned)long long 数组空间开小等问题，调试无果后我开始怀疑是不是我的思路出了问题。

如果您认为我的思路出了问题，麻烦请您告诉我正确的思路，如果您认为我写挂了，请给我一个 hack 或直接指出我的错误。

感谢您的付出，祝您 NOIP2023 rp++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


ll read() {
	ll x = 0, f = 1;
	char c;
	c = getchar();
	while(!isdigit(c)) {
		if(c == '-')  f = -1;
		c = getchar();
	}
	while(isdigit(c)){
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x * f;
}
const int maxn = 1e5 + 5;

ll n;
struct Node {
	ll a, b, c;
}a[maxn];
vector<int> G[maxn];

bool A, B, C, D;

namespace AA {
	ll ans = 0, used[maxn];
	vector<pair<ll, ll> > tmp;
	void bfs() {
		priority_queue<pair<ll, ll> > q;
		ll now = 0;
		q.push(make_pair(a[1].b, 1));
		while(!q.empty()) {
			int x = q.top().second, b = q.top().first;
			q.pop();
			if(used[x]) continue;
			used[x] = true;
			ans = max(ans, now + (a[x].a / b + (a[x].a % b) == 0 ? 0 : 1));
			now++;
			for(auto to : G[x]) {
				if(used[to]) continue;
				q.push(make_pair(a[to].b, to));
			}
		}
	}
	void main() {
		ans = (a[1].a + a[1].b - 1) / a[1].b;
		bfs();
		cout << ans << "\n";
		exit(0);
	}
}

namespace BB {
	void main() {
		ll ans = 0, now = 1;
		for(int i = 1; i <= n; i++) {
			ll x = now, high = 0;
			while(high < a[i].a) {
				high += max(a[i].c * x + a[i].b, 1ll * 1);
				x++;
			}
			ans = max(ans, x);
			now++;
		}
		cout << ans << "\n";
	}
}

int main() {
	//freopen("tree.in", "r", stdin);
	//freopen("tree.out", "w", stdout);
	n = read();
	A = B = C = D = true;
	for(int i = 1; i <= n; i++) {
		a[i].a = read(), a[i].b = read(), a[i].c = read();
		if(a[i].c != 0) A = false;
	}
	for(int i = 1, u, v; i < n; i++) {
		u = read(); v = read();
		G[u].push_back(v);
		G[v].push_back(u);
		if(v != i + 1 || u != i) B = false;
		if(u != 1) D = false;
	}
	if(A) {
		AA::main();
		return 0;
	}
	if(B) {
		BB::main();
		return 0;
	}
	cout << 1 << '\n';
	return 0;
}