感觉一条链的时候就是顺着种树，二分答案啊，不知道为什么寄了 /kel

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define iint __int128
const int N = 1e5+5;
int a[N],b[N],c[N],u,v,ans,n;
int ck(int x,int y,int id){
	int a1 = (y - x + 1) * b[id];
	iint yy = y,xx = x;
	iint a2 = (xx + yy) * (yy - xx + 1) / 2 * (__int128)(c[id]);
	int a3 = min(a2,(iint)a[id]);
	return a1 + a3;
}int gans(int id,int rr){
	int l = id,r = rr,ans = -1;
	while(l <= r){
		int mid = (l + r) / 2;
		if(ck(id,mid,id) >= a[id]) r = mid - 1,ans = mid; else l = mid + 1;
	}return ans;
}signed main(){
	//freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
	cin >> n;
	for(int i = 1;i <= n;i ++) cin >> a[i] >> b[i] >> c[i];
	for(int i = 1;i < n;i ++) cin >> u >> v;
	for(int i = 1;i <= n;i ++){
		if(c[i] < 0){
			int k = (b[i] - 1 - c[i] - 1) / (-c[i]);
			if(i > k) ans = max(ans,a[i] + i - 1);
			else{
				if(gans(i,k) != -1) ans = max(ans,gans(i,k));
				else{
					int x = ck(i,k,i);
					ans = max(ans,k + (a[i] - x));
				}
			}
		}else ans = max(ans,gans(i,1e9));
	}cout << ans;
}