#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=100000+10;
ll n,deg[MAXN],Deg[MAXN],fa[MAXN],a[MAXN],b[MAXN],c[MAXN],val[MAXN];
struct Edge {int to,nxt;}edge[MAXN<<1];
int tot,hd[MAXN];
void add_edge(int u,int v) {
	edge[++tot]={v,hd[u]},hd[u]=tot;
	edge[++tot]={u,hd[v]},hd[v]=tot;
	return ;
}
void dfs(int u,int f) {
	int flg=0;
	fa[u]=f;
	for(int i=hd[u];i;i=edge[i].nxt) {
		int v=edge[i].to;
		if(v==f) continue;
		flg++,dfs(v,u);
	}
	deg[u]=flg;
	return ;
}
ll find_t(ll a,ll b,ll c,ll t) {
	if(c>=0||t*c+b>=1) {
		__int128 _1=1;
		__int128 A=c,B=2*b-c,C=2*a-_1*c*t*t-c*t-2*b-2*b*t,Delta=B*B-4*A*C;
		__int128 ans;
		if(c==0) ans=(-C)/B;
		else ans=(-B+sqrt(Delta))/(A*2);
		while(A*ans*ans+B*ans+C>0) ans--;
		while(A*(ans+1)*(ans+1)+B*(ans+1)+C<=0) ans++;
		return ans;
	}
	ll ed=(b-1)/(-c);
	if(t-ed>=a) return t-a+1;
	return find_t(a-(t-ed),b,c,ed);
}
ll mul(ll x,ll y,ll z) {
	ll mxy=z/x+1;
	if(y>mxy) return z+1;
	return x*y;
}
ll calc(ll a,ll b,ll c,ll st,ll ed) {
	if(c>=0) {
		ll v0=b+st*c,v1=b+ed*c;
		if(v0>=a||v1>=a) return a;
		ll vala=v0+v1,valb=ed-st+1;
		if(vala%2==0) vala/=2; else valb/=2;
		return mul(vala,valb,a);
	}
	ll All=(b-1)/(-c);
	if(All<=st) return ed-st+1;
	if(All>=ed) {
		ll v0=b+st*c,v1=b+ed*c;
		if(v0>=a||v1>=a) return a;
		ll vala=v0+v1,valb=ed-st+1;
		if(vala%2==0) vala/=2; else valb/=2;
		return mul(vala,valb,a);
	}
	ll v0=b+st*c,v1=b+All*c;
	if(v0>=a||v1>=a) return a;
	ll vala=v0+v1,valb=All-st+1;
	if(vala%2==0) vala/=2; else valb/=2;
	return mul(vala,valb,a)+ed-All;
}
vector<int> candidate[MAXN];
int check(int t) {
	ffor(i,1,n) Deg[i]=deg[i];
	ffor(i,1,n) if(calc(a[i],b[i],c[i],1,t)<a[i]) return 0;
	ffor(i,1,n) val[i]=min(n,find_t(a[i],b[i],c[i],t)),candidate[i].clear();
	ffor(i,1,n) if(Deg[i]==0) candidate[val[i]].push_back(i);
	queue<int> q;
	roff(i,n,1) {
		for(auto v:candidate[i]) q.push(v);
		if(q.empty()) return 0;
		int u=q.front(); q.pop();
		if(fa[u]) {
			Deg[fa[u]]--;
			if(Deg[fa[u]]==0) {
				if(val[fa[u]]>=i) q.push(fa[u]);
				else candidate[val[fa[u]]].push_back(fa[u]);
			}
		}
	}
	return 1;
}
int bfind(int l,int r) {
	int ans=r,mid;
	while(l<=r) {
		mid=l+r>>1;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
int main() {
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n; ffor(i,1,n) cin>>a[i]>>b[i]>>c[i];
	ffor(i,1,n-1) {
		int u,v; cin>>u>>v;
		add_edge(u,v);
	}
	dfs(1,0);
	cout<<bfind(n,1000000000);
	return 0;
}

这是我今天 CSP-S T4 的代码 .

Geany 过了编译 . 而且我记得没有报错 .

但是那个对 __int128 开根号有歧义 . 现在过不了编译 .

怎么办 .