#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;
};
vector<line> hull;
bool addline(ll k, ll b, ll id){
while((int)hull.size() >= 2){
if(hull.back().k == k){
if(hull.back().b >= b){
reset[cur].emplace_back(hull.back().id);
hull.pop_back();
continue;
} else {
return 0;
}
}
if(calcx(hull.back().b - hull[hull.size() - 2].b, hull[hull.size() - 2].k - hull.back().k) >= calcx(b - hull.back().b, hull.back().k - k)){
reset[cur].emplace_back(hull.back().id);
hull.pop_back();
} else break;
}
hull.push_back({k, b, id});
return 1;
}
ll query(ll x){
int l = 0, r = (int)hull.size() - 2, pos = 0;
while(l <= r){
int mid = (l + r) / 2;
ll point = calcx(hull[mid + 1].b - hull[mid].b, hull[mid].k - hull[mid + 1].k);
if(point <= x){
pos = mid + 1;
l = mid + 1;
} else r = mid - 1;
}
return hull[pos].k*x + hull[pos].b;
}
void dfs(int v, int p, ll d){
dist[v] = d;
cur = v;
if(v) ans[v] = query(vv[v]) + dist[v]*vv[v] + s[v];
bool y = addline(-dist[v], ans[v], v);
for(pll& u : a[v]){
if(u.ff == p) continue;
dfs(u.ff, v, d + u.ss);
}
assert((int)hull.size() > 0);
if(y) hull.pop_back();
for(int i = (int)reset[cur].size() - 1; i >= 0; i--){
int u = reset[cur][i];
addline(-dist[u], ans[u], u);
}
}
void solve(){
cin >> n;
hull.reserve(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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Correct |
2 ms |
852 KB |
Output is correct |
| 3 |
Runtime error |
44 ms |
18876 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
70 ms |
28776 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
81 ms |
36516 KB |
Execution killed with signal 6 |
| 6 |
Correct |
117 ms |
23656 KB |
Output is correct |
| 7 |
Runtime error |
40 ms |
18448 KB |
Execution killed with signal 6 |
| 8 |
Runtime error |
79 ms |
35916 KB |
Execution killed with signal 8 |
| 9 |
Runtime error |
212 ms |
62868 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
477 ms |
65536 KB |
Execution killed with signal 9 |
