#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
#define line pli
using ld=long double;
struct ConvexHullTrick
{
vector<line> dt;
vector<ld> x;
struct qq
{
line a;
ld b;
bool c;
};
vector<qq>D;
void rollback(ll cc)
{
while(D.size()>cc)
{
if(D.back().c==1)
{
dt.pop_back();
x.pop_back();
}
else
{
dt.pb(D.back().a);
x.pb(D.back().b);
}
D.pop_back();
}
}
ld giao(line l1, line l2)
{
return 1. * (l2.se - l1.se) / (l1.fi - l2.fi);
}
bool chk(line l2, line l1, line l)
{
return giao(l, l1) > giao(l, l2);
}
void add(line l)
{
while (dt.size() >= 2 && !chk(dt[dt.size() - 2], dt.back(), l))
{
D.pb({dt.back(),x.back(),0});
dt.pop_back();
x.pop_back();
}
if (dt.empty())
x.pb(-inf);
else
x.pb(giao(l, dt.back()));
dt.pb(l);
D.pb({dt.back(),x.back(),1});
}
ll query(ll uoc)
{
int p = upper_bound(x.begin(), x.end(), uoc) - x.begin() - 1;
return dt[p].fi * uoc + dt[p].se;
}
}cht;
ll dp[maxN];
ll v[maxN];
ll s[maxN];
ll h[maxN];
vector<pli>g[maxN];
void dfs(ll u=1,ll p=0)
{
dp[1]=0;
if(u!=1)
{
dp[u]=cht.query(v[u])+s[u]+h[u]*v[u];
}
ll x=cht.D.size();
cht.add({-h[u],dp[u]});
for(auto zz:g[u])
{
if(zz.fi!=p)
{
h[zz.fi]=h[u]+zz.se;
dfs(zz.fi,u);
}
}
cht.rollback(x);
}
ll n;;
void solve()
{
cin >> n;
for(int i=1;i<n;i++)
{
ll u,v,w;
cin >> u >> v >> w;
g[u].pb({v,w});
g[v].pb({u,w});
}
for(int i=2;i<=n;i++)
{
cin >> s[i] >> v[i];
}
dfs();
for(int i=2;i<=n;i++) cout << dp[i]<<' ';
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message
harbingers.cpp: In member function 'void ConvexHullTrick::rollback(ll)':
harbingers.cpp:28:23: warning: comparison of integer expressions of different signedness: 'std::vector<ConvexHullTrick::qq>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
28 | while(D.size()>cc)
| ~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
6 ms |
5908 KB |
Output is correct |
3 |
Correct |
57 ms |
18796 KB |
Output is correct |
4 |
Correct |
66 ms |
22996 KB |
Output is correct |
5 |
Correct |
85 ms |
31568 KB |
Output is correct |
6 |
Runtime error |
110 ms |
34032 KB |
Memory limit exceeded |
7 |
Correct |
56 ms |
17784 KB |
Output is correct |
8 |
Execution timed out |
1072 ms |
27208 KB |
Time limit exceeded |
9 |
Execution timed out |
1075 ms |
21216 KB |
Time limit exceeded |
10 |
Execution timed out |
1073 ms |
28088 KB |
Time limit exceeded |