#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <ll, ll>;
using pil = pair <ll, ll>;
using pli = pair <ll, ll>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const ll maxN = 1e5 + 1;
ll n;
vector <pii> adj[maxN];
ll s[maxN], v[maxN];
pll cht[maxN];
ll sz = 0;
ll dp[maxN];
inline ld llersect(pll l, pll r){
return ld(r.se - l.se) / ld(l.fi - r.fi);
}
ll get(ll x){
ll l = 0, r = sz - 1;
while (l < r){
ll mid = (l + r) / 2;
if (llersect(cht[mid], cht[mid + 1]) < x) l = mid + 1;
else r = mid;
}
return cht[l].fi * x + cht[l].se;
}
ll update(pll line){
if (sz < 2 || llersect(line, cht[sz - 1]) >= llersect(cht[sz - 1], cht[sz - 2])){
return sz;
}
ll l = 1, r = sz - 1;
while (l < r){
ll mid = (l + r) / 2;
if (llersect(line, cht[mid]) < llersect(cht[mid], cht[mid - 1])) r = mid;
else l = mid + 1;
}
return l;
}
void dfs(ll u, ll p, ll dis = 0){
ll pre_size, pre_pos;
pll pre_line;
if (u == 1){
cht[sz++] = {0, 0};
}
else{
dp[u] = get(v[u]) + dis * v[u] + s[u];
pll line = {-dis, dp[u]};
pre_size = sz;
pre_pos = sz = update(line);
pre_line = cht[pre_pos];
cht[sz++] = line;
}
for (const auto &i: adj[u]){
if (i.fi == p) continue;
dfs(i.fi, u, i.se + dis);
}
if (u != 1){
sz = pre_size;
cht[pre_pos] = pre_line;
}
}
void Init(){
cin >> n;
for (ll i = 1; i < n; ++i){
ll u, v, w;
cin >> u >> v >> w;
adj[v].pb({u, w});
adj[u].pb({v, w});
}
for (ll i = 2; i <= n; ++i){
cin >> s[i] >> v[i];
}
dfs(1, 0);
for (ll i = 2; i <= n; ++i) cout << dp[i] << " ";
}
signed main(){
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
//freopen(taskname".out", "w", stdout);
}
faster;
ll tt = 1;
//cin >> tt;
while (tt--){
Init();
}
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
4 ms |
3200 KB |
Output is correct |
3 |
Correct |
75 ms |
10688 KB |
Output is correct |
4 |
Correct |
70 ms |
14788 KB |
Output is correct |
5 |
Correct |
101 ms |
18324 KB |
Output is correct |
6 |
Correct |
132 ms |
21948 KB |
Output is correct |
7 |
Correct |
69 ms |
11260 KB |
Output is correct |
8 |
Correct |
147 ms |
16504 KB |
Output is correct |
9 |
Correct |
164 ms |
18652 KB |
Output is correct |
10 |
Correct |
102 ms |
17152 KB |
Output is correct |