csp s4 求调

我是先二分答案

再预处理出每棵树最晚什么时候种（d数组）

再求每个点的子树的最小值（w数组）

最后优先队列+深搜

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll getin(){
	ll ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1; 
		c=getchar();
	}
	while(c>='0'&&c<='9') ans=(ans<<1)+(ans<<3)+(c-'0'),c=getchar();
	return ans*f;
};
const int N=100010;
const ll inf=1000000000000000010;
struct node{
	ll to,next;
}e[N<<1];
ll cnt,h[N];
void add(ll u,ll v){
	++cnt;
	e[cnt].next=h[u];
	e[cnt].to=v;
	h[u]=cnt;
}
ll n;
ll a[N],b[N],c[N],d[N],w[N];
bool vis[N];
priority_queue<pair<ll,ll> > q;
ll js(ll x,ll y,ll i){
	if(c[i]!=0){if((a[i]-(y-x+1)*b[i])/c[i]<=(x+y)*(y-x+1)/2) return inf;}
	return (x+y)*(y-x+1)/2*c[i]+(y-x+1)*b[i];
}
void dfs1(ll u){
	w[u]=d[u];
	for(ll i=h[u];i;i=e[i].next){
		ll v=e[i].to;
		if(vis[v])continue;
		vis[v]=1;
		dfs1(v);
		w[u]=min(w[u],w[v]);
	}
}
bool dfs(ll u,ll day){
	for(ll i=h[u];i;i=e[i].next){
		ll v=e[i].to;
		if(vis[v])continue;
		vis[v]=1;
		q.push(make_pair(-w[v],v));
	}
	if(!q.empty()){
		ll x=q.top().second;
		ll dd=d[x];
		q.pop();
		if(dd<=day)return false;
		return dfs(x,day+1);
	}
	return true;
}
bool check(ll x){
	for(ll i=1;i<=n;i++){
		if(c[i]>=0){
			ll l=0,r=x+1;
			while(l+1<r){
				ll mid=(l+r)>>1;
				if(js(mid,x,i)>=a[i]) l=mid;
				else r=mid;
			}
			if(l==0)return false;
			d[i]=l;
		}
		else {
			ll m=b[i]/(-c[i]);
			if(b[i]%(-c[i])==0)m--;
			if(m>x){
				ll l=0,r=x+1;
				while(l+1<r){
					ll mid=(l+r)>>1;
					if(js(mid,x,i)>=a[i]) l=mid;
					else r=mid;
				}
				if(l==0)return false;
				d[i]=l;
			}
			else {
				if(x-m>=a[i]){
					d[i]=x-a[i]+1;
					continue;
				}
				ll l=0,r=m+1;
				while(l+1<r){
					ll mid=(l+r)>>1;
					if(js(mid,m,i)+(x-m)>=a[i]) l=mid;
					else r=mid;
				}
				if(l==0)return false;
				d[i]=l;
			}
		}
	}
	
	while(!q.empty())q.pop();
	memset(vis,0,sizeof(vis));
	memset(w,0x3f,sizeof(w));
	vis[1]=1;
	dfs1(1);
	
	memset(vis,0,sizeof(vis));
	vis[1]=1;
	return dfs(1,1);
}
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	cin>>n;
	for(ll i=1;i<=n;i++){
		a[i]=getin();
		b[i]=getin();
		c[i]=getin();
	}
	for(ll i=1;i<n;i++){
		ll u,v;
		u=getin();
		v=getin();
		add(u,v);add(v,u);
	}
	ll l=0,r=1000000001;
	while(l+1<r){
		ll mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid;
	}
	cout<<r;
	fclose(stdin);
	fclose(stdout);
	return 0;
}