#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 100005
#define ALL(x) x.begin(), x.end()
struct line
{
ll m, c;
line(ll m, ll c) : m(m), c(c) {}
line() : m(0), c(0) {}
inline ll operator[](ll x) { return m*x+c; }
inline ll intersect(line &l) { if (l.m==m) return 1e18; return (ll)(c-l.c)/(l.m-m); }
};
int n, s[N], v[N];
ll rt[N], dp[N];
vector<pair<int, int>> g[N];
line cht[N]; int sz;
inline int add(line k)
{
if (!sz || sz && cht[sz].intersect(cht[sz-1]) < cht[sz-1].intersect(k)) return sz+1;
int l = 1, r = sz, z = 0;
for (; l <= r;)
{
int m = (l+r)/2;
if (cht[m].m == k.m)
{
if (cht[m].c <= k.c) z = m, l = m + 1;
else return 0;
}
else
{
if (cht[m].intersect(cht[m-1]) > cht[m-1].intersect(k)) z = m, l = m + 1;
else r = m - 1;
}
}
return z;
}
inline ll qry(ll x)
{
if (!sz) return 0;
int l = 0, r = sz - 1, z = sz;
for (;l <= r;)
{
int m = (l+r)/2;
if (cht[m].intersect(cht[m+1]) < x) l=m+1;
else r=m-1, z = m;
}
return cht[z][x];
}
void dfs(int u, int p)
{
int at, psz = sz;
dp[u] = s[u] + 1ll*v[u]*rt[u] - qry(v[u]);
dp[1] = 0;
at = add(line{rt[u], -dp[u]});
line overwrote = cht[at], nw {rt[u], -dp[u]};
if (at) cht[at] = nw, sz = at;
for (auto [w, v] : g[u]) if (v != p) rt[v] = rt[u] + w, dfs(v, u);
if (at)
sz = psz, cht[at] = overwrote;
}
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];
dfs(1, 1);
for (int i = 2; i <= n; ++i) cout << dp[i] << ' ';
return 0;
}
Compilation message
harbingers.cpp: In function 'int add(line)':
harbingers.cpp:37:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
37 | if (!sz || sz && cht[sz].intersect(cht[sz-1]) < cht[sz-1].intersect(k)) return sz+1;
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
2 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
3 |
Incorrect |
31 ms |
11604 KB |
Output isn't correct |
4 |
Incorrect |
45 ms |
14928 KB |
Output isn't correct |
5 |
Incorrect |
46 ms |
18256 KB |
Output isn't correct |
6 |
Incorrect |
75 ms |
21584 KB |
Output isn't correct |
7 |
Incorrect |
38 ms |
11860 KB |
Output isn't correct |
8 |
Incorrect |
82 ms |
15552 KB |
Output isn't correct |
9 |
Incorrect |
92 ms |
17808 KB |
Output isn't correct |
10 |
Incorrect |
74 ms |
16648 KB |
Output isn't correct |