#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 1e5;
int n;
ll dp[MAXN],t[MAXN],s[MAXN];
vector<pii>adj[MAXN];
struct line{
ll m,c;
line(ll _m,ll _c):m(_m),c(_c){}
line(){}
ll eval(ll x){return m*x+c;}
}hull[MAXN];
int szz = 0;
ll Div(ll a,ll b){return a / b + ((a^b) < 0 && (a%b));}
void dfs(int v,int u,int d){
if(v){
int l = -1,r = szz-1;
while(r-l>1){
int mid = (l+r)/2;
if(hull[mid].eval(s[v]) >= hull[mid+1].eval(s[v]))l=mid;
else r = mid;
//r is first value that has mid<mid+1
}
dp[v] = d*1LL*s[v] + hull[r].eval(s[v]) + t[v];
}
line x = line(-d,dp[v]);
int old_szz = szz;
int pos = 0;
line prev;
while(szz>=2){
line f = hull[szz-1];
line g = hull[szz-2];
if(Div(f.c - g.c , g.m - f.m) >= Div(f.c - x.c , x.m - f.m))szz--;
else break;
}
pos = szz++;
if(pos != old_szz+1)prev = hull[pos];
hull[pos] = x;
for(pii x:adj[v]){
if(x.fi==u)continue;
dfs(x.fi,v,d+x.se);
}
if(pos != old_szz+1)hull[pos] = prev;
szz = old_szz;
}
int main()
{
owo
cin>>n;
for(int i=0;i<n-1;i++){
int u,v,w;
cin>>u>>v>>w;
u--;
v--;
adj[v].pb({u,w});
adj[u].pb({v,w});
}
for(int i=1;i<n;i++)cin>>t[i]>>s[i];
dfs(0,-1,0);
for(int i=1;i<n;i++)cout<<dp[i]<<" ";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 3 |
Correct |
35 ms |
11208 KB |
Output is correct |
| 4 |
Correct |
52 ms |
15140 KB |
Output is correct |
| 5 |
Correct |
69 ms |
18768 KB |
Output is correct |
| 6 |
Correct |
86 ms |
22268 KB |
Output is correct |
| 7 |
Correct |
46 ms |
11900 KB |
Output is correct |
| 8 |
Execution timed out |
1091 ms |
15680 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1091 ms |
14532 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1088 ms |
16960 KB |
Time limit exceeded |
