有无卡常大神

#include <bits/stdc++.h>
using lint = long long;
using pii = std::pair<int, int>;
const int N = 1e5 + 10;

// #define DEBUG 1  // 调试开关
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
  char buf[MAXSIZE], *p1, *p2;
  char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
  IO() : p1(buf), p2(buf), pp(pbuf) {}

  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
  char gc() {
#if DEBUG  // 调试，可显示字符
    return getchar();
#endif
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
    return p1 == p2 ? ' ' : *p1++;
  }

  void read(int &x) {
    bool neg = false;
    x = 0;
    char ch = gc();
    for (; !isdigit(ch); ch = gc())
      if (ch == '-') neg = true;
    if (neg)
      for (; isdigit(ch); ch = gc()) x = x * 10 + ('0' - ch);
    else
      for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
  }
  
  void read(long long &x) {
    bool neg = false;
    x = 0;
    char ch = gc();
    for (; !isdigit(ch); ch = gc())
      if (ch == '-') neg = true;
    if (neg)
      for (; isdigit(ch); ch = gc()) x = x * 10 + ('0' - ch);
    else
      for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
  }

  void read(char *s) {
    char ch = gc();
    for (; isspace(ch); ch = gc());
    for (; !isspace(ch); ch = gc()) *s++ = ch;
    *s = 0;
  }

  void read(char &c) { for (c = gc(); isspace(c); c = gc()); }

  void push(const char &c) {
#if DEBUG  // 调试，可显示字符
    putchar(c);
#else
    if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
    *pp++ = c;
#endif
  }

  void write(int x) {
    bool neg = false;
    if (x < 0) {
      neg = true;
      push('-');
    }
    static int sta[40];
    int top = 0;
    do {
      sta[top++] = x % 10;
      x /= 10;
    } while (x);
    if (neg)
      while (top) push('0' - sta[--top]);
    else
      while (top) push('0' + sta[--top]);
  }

  void write(int x, char lastChar) { write(x), push(lastChar); }
} io;

struct Tree {
	int id;
	lint a, b, c;
	int lst;
	int mx; // 子树中的最小 lst 
	
	bool operator<(const Tree &x) const {
		if (mx != x.mx) return mx > x.mx;
		if (lst != x.lst) return lst > x.lst;
		if (id != x.id) return id < x.id;
		if (a != x.a) return a < x.a;
		if (b != x.b) return b < x.b;
		return c < x.c;
	}
} t[N];

bool vis[N];
std::vector<int> g[N];
int n, s[N];

__int128 f(lint u, lint x, int i) {
	if (u > x) return 0;
	lint b = t[i].b, c = t[i].c;
	
	if (c >= 0) {
		return (__int128)(x - u + 1) * b + (__int128)(u + x) * (x - u + 1) / 2 * c;
	}
	
	lint p =  (1 - b) / c;
	if (p >= x) return (__int128)(x - u + 1) * b + (__int128)(u + x) * (x - u + 1) / 2 * c;
	else if (u > p) return x - u + 1;
	return (__int128)(p - u + 1) * b + (__int128)(u + p) * (p - u + 1) / 2 * c + x - p;
}

void calc(int i, lint x) {
	lint l = 0, r = 1e9 + 1;
	while (l + 1 != r) {
		lint mid = (l + r) >> 1;
		if (f(mid, x, i) >= t[i].a) l = mid;
		else r = mid;
	}
	t[i].lst = l;
}

void dfs(int u, int f) {
	t[u].mx = t[u].lst;
	for (auto v : g[u]) {
		if (v == f) continue;
		dfs(v, u);
		t[u].mx = std::min(t[u].mx, t[v].mx);
	}
}

bool check(lint x) { // x 天内能否完成
	for (int i = 1; i <= n; ++i) {
		calc(i, x);
		if (t[i].lst < 1) return false;
	}
	
	dfs(1, 1);
	
	memset(vis, 0, sizeof(vis));
	
	std::priority_queue<Tree> heap;
	heap.push(t[1]), vis[1] = true;
	int cnt = 0;
	while (heap.size()) {
		auto cur = heap.top(); heap.pop();
		s[cur.id] = ++cnt;
		for (auto v : g[cur.id]) {
			if (!vis[v]) {
				heap.push(t[v]);
				vis[v] = true;
			}
		}
	}
	for (int i = 1; i <= n; ++i)
		if (s[i] > t[i].lst) return false;
	return true;
}

signed main() {
	io.read(n);
	for (int i = 1; i <= n; ++i) {
		io.read(t[i].a), io.read(t[i].b), io.read(t[i].c);
		t[i].id = i;
	}
	for (int i = 1, u , v; i < n; ++i) {
		io.read(u), io.read(v);
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
	lint l = 0, r = 1e9 + 1;
	while (l + 1 != r) {
		lint mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid;
	}
	io.write(r, '\n');
  return 0;
}