#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
typedef pair <ll,ll> ii;
const int N = 1e5+5;
vector <ii> g[N];
ll i,j,n,m,k,t,s[N],v[N],h[N],dp[N];
ll top=0;
ii d[N]; // line y = ax+b
struct pt
{
ll pos,top;
ii line;
};
vector <pt> list_undo;
bool bad(ii A,ii B,ii C)
{
ii ab = {B.x - A.x,B.y - A.y};
ii ac = {C.x - A.x,C.y - A.y};
return (ab.x*ac.y-ab.y*ac.x >= 0);
}
ll val(ll x,ll id)
{
return (d[id].x * x + d[id].y);
}
void add(ll x,ll y)
{
ll l = 1,r = top - 1,pos = top;
ii new_d = {x,y};
while(l<=r)
{
ll mid = (l+r)/2;
if(bad(d[mid-1],d[mid],new_d))
{
r = mid - 1;
pos = mid;
}
else
{
l = mid + 1;
}
}
list_undo.push_back({pos,top,d[pos]});
top = pos + 1;
d[pos] = new_d;
}
void undo()
{
pt pre_pt = list_undo.back();
list_undo.pop_back();
top = pre_pt.top;
d[pre_pt.pos] = pre_pt.line;
}
ll query(ll coord)
{
ll l = 0, r = top - 1;
ll ans = val(coord,l);
while (l < r) {
ll mid = (l + r) >> 1;
ll x = val(coord,mid);
ll y = val(coord,mid+1);
if (x > y) l = mid + 1; else r = mid;
ans = min(ans, min(x, y));
}
return ans;
}
void dfs(ll u,ll par)
{
if(u!=par)
{
dp[u]=query(v[u])+s[u]+v[u]*h[u];
}
add(-h[u],dp[u]);
for(auto x: g[u])
{
ll v = x.first;
ll w = x.second;
if(v==par){continue;}
h[v] = h[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,1);
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 |
5212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5724 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
11488 KB |
Output isn't correct |
| 4 |
Correct |
47 ms |
14632 KB |
Output is correct |
| 5 |
Correct |
67 ms |
17496 KB |
Output is correct |
| 6 |
Correct |
89 ms |
20524 KB |
Output is correct |
| 7 |
Correct |
38 ms |
12064 KB |
Output is correct |
| 8 |
Correct |
92 ms |
16220 KB |
Output is correct |
| 9 |
Correct |
90 ms |
17860 KB |
Output is correct |
| 10 |
Correct |
68 ms |
16540 KB |
Output is correct |
