#include <cstdio>
#include <stack>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)
#define N 200005
#define ALL(x) x.begin(), x.end()
/*
* dp[i] = cost from i to 1
*
* dp[i] = min p (dp[p] + distance(i, p) + start[i])
*
*/
int rv[N], c[N], C;
struct line
{
ll m, c;
line(ll m, ll c) : m(m), c(c) {}
ll operator[](ll x) { return m*rv[x]+c; }
};
ostream& operator<<(ostream &out, line k)
{
out << '{'<<k.m << ", " <<k.c<<'}';
return out;
}
struct lichao_rollback
{
static const size_t M = 2*N;
vector<line> t;
stack<pair<int*, int> > S;
stack<pair<line*, line> > SL;
vector<int> U, UL;
lichao_rollback() : t(M, line(0, ll(1e17))) { }
void set(int*p, int k) { S.emplace(p, *p), *p = k; }
void set(line*p, line k) { SL.emplace(p, *p), *p = k; }
void add(line k, int v, int l, int r)
{
int m = (l+r)/2, cl = k[l] <= t[v][l], cm = k[m] <= t[v][m], vl = v+1, vr = v+(m-l+1)*2;
if (cm) { line tmp = t[v]; set(&t[v], k); k = tmp; }
if (l == r) return;
if (cl != cm) add(k, vl, l, m);
else add(k, vr, m+1, r);
}
void add(line k) { save(); add(k, 0, 0, C-1); }
ll qry(ll x, int v, int l, int r)
{
if (l == r) return t[v][x];
int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2;
if (x <= m) return min(t[v][x], qry(x, vl, l, m));
return min(t[v][x], qry(x, vr, m+1, r));
}
ll qry(ll x) { save(); return qry(x, 0, 0, C-1); }
void save()
{
UL.push_back(SL.size()), U.push_back(S.size());
}
void rollback()
{
while (UL.back() < SL.size()) { auto [p, k] = SL.top(); *p = k; SL.pop(); }
while (U.back() < S.size()) { auto [p, k] = S.top(); *p = k; S.pop(); }
}
};
int n, s[N], v[N];
ll rt[N], dp[N];
vector<pair<int, int>> g[N];
void compress()
{
for (int i = 2; i <= n; ++i) c[C++] = v[i];
sort(c, C+c);
for (int i = 2; i <= n; ++i) rv[lower_bound(c, c+C, v[i]) - c] = v[i];
}
void dfs(int u, int p, lichao_rollback &lc)
{
dp[u] = s[u] + 1ll*v[u]*rt[u] + lc.qry(lower_bound(c, c+C, v[u]) - c);
//cerr << "Q " << u << ' ' << lc.qry(v[u]) << ' ' << rt[u] << ' ' << v[u] << ' ' << s[u] << endl;
dp[1] = 0;
lc.add(line{-rt[u], dp[u]});
for (auto [w, v] : g[u]) if (v != p)
{
rt[v] = rt[u] + w;
dfs(v, u, lc);
}
lc.rollback();
lc.rollback();
}
int main()
{
ShinLena;
cin >> n;
for (int u, v, w, i = 1; i < n; ++i) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);
for (int i = 2; i <= n; ++i) cin >> s[i] >> v[i];
compress();
lichao_rollback lc;
dfs(1, 1, lc);
for (int i = 2; i <= n; ++i) cout << dp[i] << ' ';
return 0;
}
Compilation message
harbingers.cpp: In member function 'void lichao_rollback::rollback()':
harbingers.cpp:83:26: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::stack<std::pair<line*, line> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | while (UL.back() < SL.size()) { auto [p, k] = SL.top(); *p = k; SL.pop(); }
| ~~~~~~~~~~^~~~~~~~~~~
harbingers.cpp:84:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::stack<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | while (U.back() < S.size()) { auto [p, k] = S.top(); *p = k; S.pop(); }
| ~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16988 KB |
Output isn't correct |
| 2 |
Incorrect |
6 ms |
17756 KB |
Output isn't correct |
| 3 |
Runtime error |
54 ms |
37700 KB |
Memory limit exceeded |
| 4 |
Runtime error |
64 ms |
36164 KB |
Memory limit exceeded |
| 5 |
Runtime error |
122 ms |
65536 KB |
Memory limit exceeded |
| 6 |
Runtime error |
129 ms |
42400 KB |
Memory limit exceeded |
| 7 |
Incorrect |
81 ms |
27536 KB |
Output isn't correct |
| 8 |
Runtime error |
150 ms |
48496 KB |
Memory limit exceeded |
| 9 |
Runtime error |
134 ms |
47308 KB |
Memory limit exceeded |
| 10 |
Runtime error |
116 ms |
44676 KB |
Memory limit exceeded |
