#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pdd pair<ld, ld>
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
typedef tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update> ordset;
#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")
ll INF = 2e18;
const ll mod = 998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll n, ll m){
if(!m) return 1;
if(m & 1) return (n * binpow(n, m - 1)) % mod;
ll b = binpow(n, m / 2);
return (b*b) % mod;
}
int n, cur;
vector<ll> dist, s, vv, ans;
vector<vector<int>> reset;
vector<vector<pll>> a;
ll calcx(ll a, ll b){
ll delta = (bool)(a % b);
if((a > 0 && b > 0) || (a < 0 && b < 0)) return a / b + delta;
return a / b;
}
struct line{
ll k, b, id;
mutable function<const line*()> succ;
bool operator<(const line otherline) const{
if(otherline.b == INF){
auto nxt = succ();
if(!nxt) return 0;
return calcx(nxt->b - b, k - nxt->k) <= otherline.k;
}
if(otherline.k == k) return b < otherline.b;
return k > otherline.k;
}
};
struct chl : multiset<line>{
bool badline(iterator y){
if(y == begin() || next(y) == end()) return 0;
ll point1, point2;
point1 = calcx(y->b - prev(y)->b, prev(y)->k - y->k);
point2 = calcx(next(y)->b - y->b, y->k - next(y)->k);
return point1 >= point2;
}
const line* addline(ll k, ll b, ll id){
auto y = insert({k, b, id});
if(y != begin() && prev(y)->k == k){
erase(y);
return 0;
}
if(next(y) != end() && next(y)->k == k){
reset[cur].push_back(next(y)->id);
erase(next(y));
}
if(badline(y)){
erase(y);
return 0;
}
y->succ = [=](){return next(y) == end() ? 0 : &*next(y);};
while(y != begin() && badline(prev(y))){
reset[cur].push_back(prev(y)->id);
erase(prev(y));
}
while(next(y) != end() && badline(next(y))){
reset[cur].push_back(next(y)->id);
erase(next(y));
}
return &*y;
}
ll query(ll x, ll id){
const line l = *lower_bound({x, INF, id});
return l.k*x + l.b;
}
void printlines(){
auto y = begin();
while(y != end()){
cout << y->k << ' ' << y->b << ' ' << y->id << '\n';
y = next(y);
}
}
};
chl hull;
void dfs(int v, int p, ll d){
dist[v] = d;
cur = v;
if(v) ans[v] = hull.query(vv[v], v) + dist[v]*vv[v] + s[v];
auto y = hull.addline(-dist[v], ans[v], v);
for(pll& u : a[v]){
if(u.ff == p) continue;
dfs(u.ff, v, d + u.ss);
}
if(y) hull.erase({y->k, y->b, y->id});
for(int u : reset[v]) hull.addline(-dist[u], ans[u], u);
}
void solve(){
cin >> n;
ans.resize(n);
a.resize(n);
reset.resize(n);
vv.resize(n);
s.resize(n);
dist.resize(n, 0);
for(int i = 0; i < n - 1; i++){
int u, v;
ll w;
cin >> u >> v >> w;
u--; v--;
a[u].push_back({v, w});
a[v].push_back({u, w});
}
for(int i = 1; i < n; i++) cin >> s[i] >> vv[i];
dfs(0, -1, 0);
for(int i = 1; i < n; i++) cout << ans[i] << ' ';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
freopen("harbingers.in", "r", stdin);
freopen("harbingers.out", "w", stdout);
int tt;
//cin >> tt;
tt = 1;
while (tt--) {
solve();
#ifdef LOCAL
cout << "__________________________________" << endl;
#endif
}
#ifdef LOCAL
cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << "sec" << '\n';
#endif
return 0;
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:161:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
161 | freopen("harbingers.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:162:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
162 | freopen("harbingers.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
