2log 做法求卡常

#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;

#define lint __int128
const int N = 1e5 + 5;

int n, u, v, fa[N], p[N], head[N], tot, s[N], dep[N]; // s[u]: 节点 u 最晚在 i 时刻被种树
lint a[N], b[N], c[N];
bool vis[N];

/*
	max(b[i] + d * c[i], 1) + max(b[i] + (d + 1) * c[i], 1) + ... + (b[i] + t * c[i], 1) >= a[i]
*/

struct edge
{
	int to, nxt;
} e[N << 1];

inline void addedge(int u, int v)
{
	e[++tot] = {v, head[u]};
	head[u] = tot;
}

inline lint ceildiv(lint x, lint y)
{
	return x / y + (x % y != 0);
}

inline lint floordiv(lint x, lint y)
{
	return x / y;
}

/*
b[i] + tu * c[i]

b[i] + t * c[i]
*/

bool judge(int i, int d, int t)
{
	lint h, tu;
	if(!c[i]) h = b[i] * (t - d + 1);
	else
	{
		// tu 表示 >= 1 与 <= 1 的转折点
		/*
			b[i] + tu * c[i] >= 1
			tu * c[i] >= 1 - b[i]
			
			tu >= (1 - b[i]) / c[i]    (c[i] > 0)
			tu <= (1 - b[i]) / c[i]    (c[i] < 0)
		*/
		if(c[i] > 0)
		{
			tu = max((lint) d, ceildiv(-b[i] + 1, c[i]));
			h = tu > t ? t - d + 1 : (tu - d) + ((b[i] + tu * c[i]) + (b[i] + t * c[i])) * (t - tu + 1) / 2;
		}
		else
		{
			tu = min((lint) t, floordiv(-b[i] + 1, c[i]));
			h = tu < d ? t - d + 1 : ((b[i] + d * c[i]) + (b[i] + tu * c[i])) * (tu - d + 1) / 2 + (t - tu);
		}
	}
	return (h >= a[i]);
}

inline int update(int u)
{
	if(vis[u] || !u) return 0;
	vis[u] = 1;
	return update(fa[u]) + 1;
}

inline bool cmp(int x, int y)
{
	return s[x] < s[y];
}

bool check(int t)
{
	memset(vis, 0, sizeof vis);
	for(int i = 1; i <= n; i++)
	{
		int L = 1, R = t, pt;
		if(!judge(i, 1, t)) return 0;
		while(L <= R)
		{
			int mid = (L + R) >> 1;
			if(judge(i, mid, t)) pt = mid, L = mid + 1;
			else R = mid - 1;
		}
		s[i] = pt;
		if(s[i] < dep[i]) return 0;
	}
	sort(p + 1, p + n + 1, cmp);
	int cnt = 0;
	for(int i = 1; i <= n; i++)
	{
		cnt += update(p[i]);
		if(cnt > s[p[i]]) return 0;
	}
	return 1;
}

void dfs(int u)
{
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if(v != fa[u]) dep[v] = dep[u] + 1, fa[v] = u, dfs(v);
	}
	return;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) p[i] = i;
	for(int i = 1; i <= n; i++)
		scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);
	for(int i = 1; i < n; i++)
	{
		scanf("%d %d", &u, &v);
		addedge(u, v);
		addedge(v, u);
	}
	dfs(1);
	int l = n, r = 1e9, ans = n;
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d", ans);
	return 0;
}