#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const ll INF = 1e18;
int N;
vector<pii> adj[MAXN+10];
ll L[MAXN+10], S[MAXN+10], V[MAXN+10], dp[MAXN+10];
struct Line { ll a, b; };
long double cross(const Line &p, const Line &q) { return ((long double)(q.b-p.b))/(p.a-q.a); }
struct CHT
{
vector<Line> S; int sz=0;
vector<int> S1; vector<Line> S2;
void update(Line p)
{
S1.push_back(sz);
if(sz!=0 && S[sz-1].a==p.a)
{
if(S[sz-1].b<=p.b)
{
S2.push_back(S[sz-1]);
return;
}
else sz--;
}
int lo=0, hi=sz;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(mid==0 || cross(S[mid], S[mid-1])<cross(S[mid], p)) lo=mid;
else hi=mid;
}
if(hi==S.size()) S.push_back({-1, -1});
sz=hi;
S2.push_back(S[sz]);
S[sz++]=p;
}
ll query(ll x)
{
int lo=0, hi=sz;
while(lo+1<hi)
{
int mid=lo+hi>>1;
long double now;
if(mid==0) now=-1e9;
else now=cross(S[mid], S[mid-1]);
if(now<=x) lo=mid;
else hi=mid;
}
return S[lo].a*x+S[lo].b;
}
void restore()
{
S[sz-1]=S2.back(); S2.pop_back();
sz=S1.back(); S1.pop_back();
}
};
CHT cht;
void dfs1(int now, int bef, ll dep)
{
L[now]=dep;
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs1(nxt.first, now, dep+nxt.second);
}
}
void dfs2(int now, int bef)
{
if(now!=1) dp[now]=cht.query(V[now])+S[now]+L[now]*V[now];
cht.update({-L[now], dp[now]});
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs2(nxt.first, now);
}
cht.restore();
}
int main()
{
int i, j;
scanf("%d", &N);
for(i=1; i<N; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for(i=2; i<=N; i++) scanf("%lld%lld", &S[i], &V[i]);
dfs1(1, 1, 0);
dfs2(1, 1);
for(i=2; i<=N; i++) printf("%lld ", dp[i]);
}
Compilation message
harbingers.cpp: In member function 'void CHT::update(Line)':
harbingers.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=lo+hi>>1;
~~^~~
harbingers.cpp:42:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(hi==S.size()) S.push_back({-1, -1});
~~^~~~~~~~~~
harbingers.cpp: In member function 'll CHT::query(ll)':
harbingers.cpp:53:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=lo+hi>>1;
~~^~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:99:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
harbingers.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
harbingers.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:109:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=2; i<=N; i++) scanf("%lld%lld", &S[i], &V[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
9 ms |
3328 KB |
Output is correct |
| 3 |
Correct |
61 ms |
12648 KB |
Output is correct |
| 4 |
Correct |
114 ms |
17088 KB |
Output is correct |
| 5 |
Correct |
123 ms |
21696 KB |
Output is correct |
| 6 |
Correct |
167 ms |
25708 KB |
Output is correct |
| 7 |
Correct |
92 ms |
13296 KB |
Output is correct |
| 8 |
Correct |
192 ms |
19104 KB |
Output is correct |
| 9 |
Correct |
161 ms |
21604 KB |
Output is correct |
| 10 |
Correct |
150 ms |
20004 KB |
Output is correct |
