#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){
//cout<<v<<" "<<szz<<'\n';
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;
if(szz<2)pos = szz;
else{
int l =1,r=szz-1;
while(r>=l){
int mid = (l+r)/2;
line f = hull[mid-1];
line g = hull[mid];
if(Div(f.c - g.c,g.m - f.m) < Div(g.c - x.c,x.m-g.m))l = mid+1;
else r=mid-1;
}
pos = l;
}
szz = pos+1;
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 |
3020 KB |
Output is correct |
| 3 |
Correct |
47 ms |
9880 KB |
Output is correct |
| 4 |
Correct |
67 ms |
13496 KB |
Output is correct |
| 5 |
Correct |
62 ms |
16584 KB |
Output is correct |
| 6 |
Correct |
89 ms |
19780 KB |
Output is correct |
| 7 |
Correct |
49 ms |
10156 KB |
Output is correct |
| 8 |
Correct |
120 ms |
14656 KB |
Output is correct |
| 9 |
Correct |
108 ms |
16984 KB |
Output is correct |
| 10 |
Correct |
89 ms |
15804 KB |
Output is correct |
