#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
const int N = 1e5+5;
typedef pair <ll,ll> ii;
vector <ii> g[N];
ll i,j,n,m,k,t,dp[N],s[N],v[N],d[N],top;
struct operation
{
ll pos,top;
ii overwrite;
operation(ll _p,ll _t,ii _o)
{
pos=_p;
top=_t;
overwrite=_o;
}
};
vector <operation> undolist;
ii line[N];
ll dt(ll x,ii d)
{
return (d.x*x+d.y);
}
bool bad(ii a,ii b,ii c)
{
return ((b.y-a.y)*(c.x-a.x)<=(c.y-a.y)*(b.x-a.x));
}
ll getmin(ll x)
{
ll l=0,r=top-1,ans=dt(x,line[l]);
while(l<r)
{
ll mid=(l+r)/2;
ll val1=dt(x,line[mid]);
ll val2=dt(x,line[mid+1]);
if(val1>val2){l=mid+1;}
else {r=mid-1;}
ans=min(ans,min(val1,val2));
}
return ans;
}
bool insertline(ii newline)
{
ll l=1,r=top-1,k=top;
while(l<=r)
{
ll mid=(l+r)/2;
if(bad(line[mid-1],line[mid],newline))
{
k=mid;
r=mid-1;
}
else {l=mid+1;}
}
undolist.push_back(operation(k,top,line[k]));
top=k+1;
line[k]=newline;
return 1;
}
void undo()
{
operation ope=undolist.back();
undolist.pop_back();
top=ope.top;
line[ope.pos]=ope.overwrite;
}
void dfs(ll u,ll par)
{
if(u>1)
{
dp[u]=getmin(v[u])+s[u]+v[u]*d[u];
}
insertline({-d[u],dp[u]});
for(auto x: g[u])
{
ll V=x.x;
ll W=x.y;
if(V==par){continue;}
d[V]=d[u]+W;
dfs(V,u);
}
undo();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(ll i=1;i<n;i++)
{
ll U,V,W;
cin>>U>>V>>W;
g[U].push_back({V,W});
g[V].push_back({U,W});
}
for(ll i=2;i<=n;i++)
{
cin>>s[i]>>v[i];
}
dfs(1,0);
for(ll i=2;i<=n;i++)
{
cout<<dp[i]<<" ";
}
return 0;
}
/*
5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7788 KB |
Output is correct |
| 3 |
Incorrect |
30 ms |
14532 KB |
Output isn't correct |
| 4 |
Correct |
48 ms |
17696 KB |
Output is correct |
| 5 |
Correct |
51 ms |
21956 KB |
Output is correct |
| 6 |
Correct |
70 ms |
24304 KB |
Output is correct |
| 7 |
Correct |
36 ms |
15300 KB |
Output is correct |
| 8 |
Incorrect |
68 ms |
19672 KB |
Output isn't correct |
| 9 |
Correct |
66 ms |
20864 KB |
Output is correct |
| 10 |
Correct |
64 ms |
19540 KB |
Output is correct |
