题目链接：https://www.luogu.com.cn/problem/P9755

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
#define int __int128
int a[N],b[N],c[N],dep[N];
struct node
{
	int to;
	int nxt;
}t[N];
int head[N];
int cnt;
void dfs(int x,int fa)
{
	for(int i = head[x];i;i = t[i].nxt)
	{
		int v = t[i].to;
		if(v!=fa)
		{
			dep[v] = dep[x]+1;
			dfs(v,x);
		}
	}
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
signed main()
{
	int n;
	n = read();
	for(int i = 1;i<=n;i++)
	{
		a[i] = read();
		b[i] = read();
		c[i] = read();
	}
	for(int i = 1;i<n;i++)
	{
		int x,y;
		x = read();
		y = read();
		cnt++;
		t[cnt].to = y;
		t[cnt].nxt = head[x];
		head[x] = cnt;
		cnt++;
		t[cnt].to = x;
		t[cnt].nxt = head[y];
		head[y] = cnt;
	}
	dep[1] = 1;
	dfs(1,0);
	int l = n,r = 1e9,ans = 0;
	while(l<=r)
	{
		int mid = (l+r)/2;
		int flag = 1;
		for(int i = 1;i<=n;i++)
		{
			int l1 = 1,r1 = 1e9,ans1 = 0;
			while(l1<=r1)
			{
				int mid1 = (l1+r1)/2;
				int t = 0;
				if(c[i]<0)
				{
					int s = (1-b[i])/c[i];
					int w = 0;
					int day = min(max(s-dep[i]+1,w),mid1);
					t = ((dep[i]+dep[i]+mid1-1)*day/2)*c[i]+day*b[i]+mid1-day;
				}
				else
				{
					t = (dep[i]+dep[i]+mid1-1)*mid1/2*c[i]+mid1*b[i];
				}
				if(t>=a[i])
				{
					ans1 = mid1;
					r1 = mid1-1;					
				}
				else
				{
					l1 = mid1+1;
				}
			}
			if(dep[i]+ans1-1>mid||mid<dep[i])
			{
				flag = 0;
				break;
			}
		}
		if(flag == 1)
		{
			ans = mid;
			r = mid-1;
		}
		else
		{
			l = mid+1;
		}
	}
	write(ans);
    return 0;
}