| 123456789 |
- #include <algorithm>
- #include <cstdint>
- #include <iostream>
- #include <queue>
- #include <vector>
- using namespace std;using i128=__int128_t;
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<long long>a(n),b(n),c(n);for(int i=0;i<n;++i)cin>>a[i]>>b[i]>>c[i];vector<vector<int>>children(n);vector<int>parent(n,-1);for(int i=1,u,v;i<n;++i){cin>>u>>v;--u;--v;children[u].push_back(v);children[v].push_back(u);}vector<int>order{0};for(size_t i=0;i<order.size();++i){int u=order[i];for(int v:children[u])if(v!=parent[u])parent[v]=u,order.push_back(v);}
- auto growth=[&](int i,long long start,long long finish)->i128{if(start>finish)return 0;i128 count=finish-start+1;if(c[i]>=0)return count*b[i]+(i128)c[i]*(start+finish)*count/2;long long z=(b[i]-1)/(-c[i]);long long high=min(finish,z);i128 sum=0;if(high>=start){i128 cnt=high-start+1;sum=cnt*b[i]+(i128)c[i]*(start+high)*cnt/2;}long long ones=finish-max(high,start-1);return sum+ones;};
- auto feasible=[&](long long days){if(days<n)return false;vector<long long>deadline(n);for(int i=0;i<n;++i){if(growth(i,1,days)<a[i])return false;long long lo=1,hi=days;while(lo<hi){long long mid=(lo+hi+1)/2;if(growth(i,mid,days)>=a[i])lo=mid;else hi=mid-1;}deadline[i]=lo;}vector<int>remaining(n);priority_queue<pair<long long,int>>heap;for(int u=0;u<n;++u){for(int v:children[u])if(parent[v]==u)++remaining[u];if(remaining[u]==0)heap.push({deadline[u],u});}for(int time=n;time>=1;--time){if(heap.empty())return false;auto[ddl,u]=heap.top();heap.pop();if(ddl<time)return false;int p=parent[u];if(p>=0&&--remaining[p]==0)heap.push({deadline[p],p});}return true;};long long lo=n,hi=1000000000LL;while(lo<hi){long long mid=(lo+hi)/2;if(feasible(mid))hi=mid;else lo=mid+1;}cout<<lo<<'\n';}
|
