#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+4;
const ll INF = 1e18;
int s[N], v[N];
ll dp[N];
vector<array<int,2>> e[N];
ll f(ll a, ll b, int x)
{
return a*x+b;
}
struct LiChao
{
struct node
{
ll a = 0, b = 0;
node *l, *r;
};
int n;
node *root;
deque<node> buffer;
vector<node*> cur;
stack<vector<node*>> stk1;
stack<vector<array<ll,2>>> stk2;
node *newnode()
{
buffer.emplace_back();
return &buffer.back();
}
LiChao(int n) : n(n) {root = newnode();}
void update(node *&v, int l, int r, ll a, ll b)
{
if (!v)
v=newnode();
int m=l+(r-l)/2;
if (f(a,b,m)<f(v->a,v->b,m))
{
swap(a,v->a);
swap(b,v->b);
cur.emplace_back(v);
stk2.top().push_back({a,b});
}
if (l==r)
return;
if (f(a,b,l)<f(v->a,v->b,l))
update(v->l,l,m,a,b);
else if (f(a,b,r)<f(v->a,v->b,r))
update(v->r,m+1,r,a,b);
}
void update(ll a, ll b)
{
cur.clear();
stk2.push({});
update(root,0,n,a,b);
stk1.push(cur);
}
ll query(node *v, int l, int r, int x)
{
if (x<l||r<x||!v)
return INF;
if (l==r)
return f(v->a,v->b,x);
int m=l+(r-l)/2;
return min({f(v->a,v->b,x),query(v->l,l,m,x),query(v->r,m+1,r,x)});
}
ll query(int x)
{
return query(root,0,n,x);
}
void rollback()
{
for (int i=0;i<(int)stk1.top().size();++i)
{
stk1.top()[i]->a = stk2.top()[i][0];
stk1.top()[i]->b = stk2.top()[i][1];
}
stk1.pop();
stk2.pop();
}
};
LiChao lct(1e9);
void dfs(int c, int p, int h)
{
dp[c]=1LL*v[c]*h+s[c]+lct.query(v[c]);
lct.update(-h,dp[c]);
for (auto i : e[c])
if (i[0]!=p)
dfs(i[0],c,h+i[1]);
lct.rollback();
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n,x,y,z;
cin>>n;
for (int i=1;i<n;++i)
{
cin>>x>>y>>z;
e[x].push_back({y,z});
e[y].push_back({x,z});
}
for (int i=2;i<=n;++i)
cin>>s[i]>>v[i];
dfs(1,0,0);
for (int i=2;i<=n;++i)
cout<<dp[i]<<" ";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
6 ms |
3788 KB |
Output is correct |
3 |
Correct |
93 ms |
28360 KB |
Output is correct |
4 |
Runtime error |
209 ms |
63372 KB |
Memory limit exceeded |
5 |
Runtime error |
154 ms |
38468 KB |
Memory limit exceeded |
6 |
Runtime error |
202 ms |
41716 KB |
Memory limit exceeded |
7 |
Correct |
125 ms |
17920 KB |
Output is correct |
8 |
Runtime error |
207 ms |
47048 KB |
Memory limit exceeded |
9 |
Runtime error |
245 ms |
60756 KB |
Memory limit exceeded |
10 |
Runtime error |
212 ms |
55992 KB |
Memory limit exceeded |