#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi first
#define se second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;
/** END OF TEMPLATE **/
const int mxN = 1e5 + 5;
typedef pair<int, int> pii;
int n;
vector<pii> g[mxN];
ll f[mxN], s[mxN], t[mxN];
struct line {
ll a, b;
line() = default;
line(ll a_, ll b_) : a(a_), b(b_) {}
ll f(ll x) { return a*x + b; }
};
struct opt {
bool state;
line L;
opt() = default;
opt(int state_, line L_) : state(state_), L(L_) {}
};
line Y[mxN];
struct CHTrick {
int sz;
CHTrick() { sz = 0; }
bool invalid(const line &l1, const line &l2, const line &l3) {
return (long double)(l3.b - l1.b)/(l1.a - l3.a) >= (long double)(l2.b - l1.b)/(l1.a - l2.a);
}
stack<opt> add(line L) {
stack<opt> st;
while(sz >= 2 && invalid(Y[sz-2], Y[sz-1], L)) {
sz--;
st.push({1, line(0, 0)});
}
st.push({0, Y[sz+1]});
Y[++sz] = L;
return st;
}
ll getMin(ll x) {
int l = 0, r = sz-1;
while(l < r) {
int mid = (l + r) >> 1;
if(Y[mid].f(x) > Y[mid+1].f(x)) l = mid+1;
else r = mid;
}
return Y[l].f(x);
}
};
int d[mxN];
CHTrick CH;
void dfs(int u, int par) {
stack<opt> st = CH.add(line(d[u], f[u]));
for(auto &it : g[u]) {
int v = it.fi; ll c = it.se;
if(v == par) continue;
d[v] = d[u] + c;
f[v] = CH.getMin(-t[v]) + s[v] + 1ll*t[v]*d[v];
dfs(v, u);
}
while(st.size()) {
opt tmp = st.top();
if(tmp.state) CH.sz++;
else {
Y[CH.sz] = tmp.L;
CH.sz--;
}
st.pop();
}
}
int main()
{
FastIO;
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
cin >> n;
FOR(i, 1, n-1) {
int u, v, c; cin >> u >> v >> c;
g[u].PB({v, c}); g[v].PB({u, c});
}
FOR(i, 2, n)
cin >> s[i] >> t[i];
dfs(1, 0);
FOR(i, 2, n) cout << f[i] << ' ';
return 0;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
4820 KB |
Output isn't correct |
| 3 |
Runtime error |
43 ms |
38928 KB |
Memory limit exceeded |
| 4 |
Runtime error |
64 ms |
56444 KB |
Memory limit exceeded |
| 5 |
Runtime error |
76 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
88 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Incorrect |
65 ms |
30356 KB |
Output isn't correct |
| 8 |
Runtime error |
106 ms |
44444 KB |
Memory limit exceeded |
| 9 |
Runtime error |
186 ms |
58856 KB |
Memory limit exceeded |
| 10 |
Runtime error |
89 ms |
52132 KB |
Memory limit exceeded |
