#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define nl '\n'
#define deb(x) cerr << #x" = " << x << nl
#define in() ( { int a ; scanf("%d", &a); a; } )
const int N = 1e5 + 9;
const int mod = 1e9 + 7;
struct Line {
int k; ll d;
ll eval(int x) {
return 1LL * k * x + d;
}
};
struct LiChaoNode {
Line line;
int l, r;
LiChaoNode(){line = Line({0, numeric_limits<long long>::max() / 2});l = 0, r = 0;}
LiChaoNode(Line line) : line(line), l(0), r(0) {}
}t[9 * N];
int T;
vector<int> coord;
int upd(int pre, Line nw, int l, int r)
{
int m = (l + r) / 2;
int id = ++T;
t[id].line = t[pre].line;
bool lef = nw.eval(coord[l]) < t[id].line.eval(coord[l]);
bool mid = nw.eval(coord[m]) < t[id].line.eval(coord[m]);
if(mid) swap(t[id].line, nw);
if(l == r) return id;
if(lef != mid){
if(!t[pre].l) t[id].l = ++T, t[T] = LiChaoNode(nw);
else t[id].l = upd(t[pre].l, nw, l, m);
t[id].r = t[pre].r;
}
else{
if(!t[pre].r) t[id].r = ++T, t[T] = LiChaoNode(nw);
else t[id].r = upd(t[pre].r, nw, m + 1, r);
t[id].l = t[pre].l;
}
return id;
}
ll query(int cur, int x, int l, int r)
{
ll val = t[cur].line.eval(x);
int m = (l + r) / 2;
if(l < r)
{
if(x <= coord[m] && t[cur].l) val = min(val, query(t[cur].l, x, l, m));
if(x > coord[m] && t[cur].r) val = min(val, query(t[cur].r, x, m + 1, r));
}
return val;
}
struct PersistentLiChaoTree
{
int L, R;
vector<int> roots;
PersistentLiChaoTree(){roots = {1}; T = 1;}
PersistentLiChaoTree(int L, int R) : L(L), R(R) {
T = 1;
roots.push_back(1);
}
void add_line(Line line) {
int root = upd(roots.back(), line, L, R);
roots.push_back(root);
}
ll get(int i, int x) {
return query(roots[i], x, L, R);
}
}lt;
ll sum[N];
vector<pair<int, int>> g[N];
void dfs(int u, int pre = 0)
{
for(auto x: g[u]){
int v = x.first, d = x.second;
if(v == pre) continue;
sum[v] = sum[u] + d;
dfs(v, u);
}
}
ll ans[N];
int rev[N];
int p[N], s[N];
void yo(int u, int pre = 0)
{
for(auto x: g[u]){
int v = x.first;
if(v == pre) continue;
ans[v] = lt.get((int)lt.roots.size() - 1, p[v]) + sum[v] * p[v] + s[v];
int sz = lt.roots.size();
lt.add_line(Line({-sum[v], ans[v]}));
yo(v, u);
lt.roots.pop_back();
}
}
int main()
{
int n; cin >> n;
for(int i = 1; i < n; i++){
int u, v, d; cin >> u >> v >> d;
g[u].eb(v, d);
g[v].eb(u, d);
}
for(int i = 2; i <= n; i++) cin >> s[i] >> p[i], coord.eb(p[i]);
sort(coord.begin(), coord.end());
coord.erase(unique(coord.begin(), coord.end()), coord.end());
dfs(1);
T = 0;
lt = PersistentLiChaoTree(0, coord.size() - 1);
lt.add_line(Line({0, 0}));
yo(1);
for(int i = 2; i <= n; i++) cout << ans[i] << ' ';
return 0;
}
Compilation message
harbingers.cpp: In function 'void yo(int, int)':
harbingers.cpp:102:27: warning: narrowing conversion of '- sum[v]' from 'long long int' to 'int' inside { } [-Wnarrowing]
lt.add_line(Line({-sum[v], ans[v]}));
^~~~~~~
harbingers.cpp:101:13: warning: unused variable 'sz' [-Wunused-variable]
int sz = lt.roots.size();
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
23804 KB |
Output is correct |
| 2 |
Correct |
23 ms |
24312 KB |
Output is correct |
| 3 |
Correct |
149 ms |
31476 KB |
Output is correct |
| 4 |
Runtime error |
210 ms |
35060 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 5 |
Runtime error |
290 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
348 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Correct |
204 ms |
31852 KB |
Output is correct |
| 8 |
Runtime error |
338 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
328 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
292 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
