#include<bits/stdc++.h>
using namespace std;
const int MN = 1e5 + 5;
#define lc ind<<1
#define rc ind<<1|1
int d[MN], s[MN], v[MN], st[MN], ed[MN], tt;
long long go[MN];
vector<array<int,2>> adj[MN];
long double intersect (int i, int j) {
return (long double)(go[j]-go[i]) / (d[j]-d[i]);
}
bool bad (int i, int j, int k) {
return (__int128)(d[j] - d[i]) * (go[k] - go[i]) <= (__int128)(go[j] - go[i]) * (d[k] - d[i]);
}
long long get (vector<int> &v, int x) {
if (v.empty()) return 1e18;
int low = 1, high = (int)v.size() - 1, mid, ans = 0;
while (low <= high) {
mid = (low + high) / 2;
if (go[v[mid]] - go[v[mid-1]] <= (long long)x * (d[v[mid]] - d[v[mid-1]])) low = (ans = mid) + 1;
else high = mid - 1;
}
return go[v[ans]] - (long long)d[v[ans]] * x;
}
vector<int> hull[MN<<2];
void update (int ind, int tl, int tr, int l, int r, int i) {
if (tl > r || tr < l) return;
if (l <= tl && tr <= r) {
while ((int)hull[ind].size() > 1 && bad(hull[ind].end()[-2],hull[ind].back(),i))
hull[ind].pop_back();
hull[ind].push_back(i);
return;
}
int mid = (tl + tr) / 2;
update(lc,tl,mid,l,r,i); update(rc,mid+1,tr,l,r,i);
}
long long query (int ind, int tl, int tr, int pos, int x) {
long long ret = get(hull[ind],x);
if (tl == tr) return ret;
int mid = (tl + tr) / 2;
if (pos <= mid) ret = min(ret,query(lc,tl,mid,pos,x));
else ret = min(ret,query(rc,mid+1,tr,pos,x));
return ret;
}
void init (int cur, int p = -1) {
st[cur] = ++tt;
for (auto &[i,w] : adj[cur]) if (i != p) {
d[i] = d[cur] + w;
init(i,cur);
}
ed[cur] = tt;
}
void dfs (int cur, int p = -1) {
if (~p) go[cur] = query(1,1,tt,st[cur],v[cur]) + (long long)d[cur] * v[cur] + s[cur];
update(1,1,tt,st[cur],ed[cur],cur);
for (auto [i,w] : adj[cur]) if (i != p) dfs(i,cur);
}
int main () {
int n; scanf ("%d",&n);
for (int i = 1; i < n; i++) {
int a,b,w; scanf ("%d %d %d",&a,&b,&w);
adj[a].push_back({b,w}); adj[b].push_back({a,w});
}
for (int i = 2; i <= n; i++) scanf ("%d %d",&s[i],&v[i]);
init(1);
dfs(1);
for (int i = 2; i <= n; i++) printf ("%lld%c",go[i]," \n"[i==n]);
return 0;
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:59:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
59 | int n; scanf ("%d",&n);
| ~~~~~~^~~~~~~~~
harbingers.cpp:61:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
61 | int a,b,w; scanf ("%d %d %d",&a,&b,&w);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:64:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
64 | for (int i = 2; i <= n; i++) scanf ("%d %d",&s[i],&v[i]);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 2 |
Correct |
13 ms |
12524 KB |
Output is correct |
| 3 |
Correct |
100 ms |
20332 KB |
Output is correct |
| 4 |
Correct |
163 ms |
24428 KB |
Output is correct |
| 5 |
Correct |
203 ms |
26924 KB |
Output is correct |
| 6 |
Correct |
240 ms |
29932 KB |
Output is correct |
| 7 |
Correct |
156 ms |
22636 KB |
Output is correct |
| 8 |
Correct |
278 ms |
28264 KB |
Output is correct |
| 9 |
Correct |
281 ms |
32104 KB |
Output is correct |
| 10 |
Correct |
235 ms |
31464 KB |
Output is correct |
