#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef ll num_t;
const num_t oo = (num_t) 1e9;
struct func_t {
num_t a, b;
func_t(num_t a = 0, num_t b = oo) : a(a), b(b) {}
num_t query(num_t x) {return a * x + b;}
};
struct node_t {
node_t *l, *r;
func_t f;
node_t(node_t* l = 0, node_t* r = 0, func_t f = func_t()) : l(l), r(r), f(f) {}
num_t query(num_t x) {return f.query(x);}
};
node_t* upd(node_t* p, int l, int r, int L, int R, func_t f) {
if (l > R || r < L) return p;
int M = L + (R - L >> 1);
node_t* res = p ? new node_t(p->l, p->r, p->f) : new node_t();
if (l <= L && r >= R) {
int fl = f.query(L) >= (p ? p->query(L) : oo);
int fr = f.query(R) >= (p ? p->query(R) : oo);
if (fl && fr) return res;
if (!fl && !fr) {
res->f = f;
return res;
}
int fm1 = f.query(M) >= (p ? p->query(M) : oo);
if (fl && fm1) {
res->r = upd(res->r, l, r, M + 1, R, f);
return res;
}
if (!fl && !fm1) {
res->r = upd(res->r, l, r, M + 1, R, res->f);
res->f = f;
return res;
}
int fm2 = f.query(M + 1) >= (p ? p->query(M + 1) : oo);
if (fm2 && fr) {
res->l = upd(res->l, l, r, L, M, f);
return res;
}
if (!fm2 && !fr) {
res->l = upd(res->l, l, r, L, M, res->f);
res->f = f;
return res;
}
assert(0);
}
res->l = upd(res->l, l, r, L, M, f);
res->r = upd(res->r, l, r, M + 1, R, f);
return res;
}
node_t* upd(node_t* p, int l, int r, int L, int R, num_t a, num_t b) {
return upd(p, l, r, L, R, func_t(a, b));
}
num_t query(node_t* p, int i, int L, int R) {
if (!p) return oo;
if (i < L || i > R) return oo;
num_t res = p->query(i);
if (L < R) {
res = min(res, query(p->l, i, L, L + R >> 1));
res = min(res, query(p->r, i, (L + R >> 1) + 1, R));
}
return res;
}
const int MM = 1e5+5;
int n,p[MM],s[MM],dep[MM]; ll dp[MM];
vector<pi> adj[MM];
void dfs(int u, int pa, node_t* t){
dp[u] = query(t,s[u],-1e9,1e9) + p[u] + 1ll*s[u]*dep[u];
if(u == 1) dp[u] = 0;
auto nxt = upd(t,-1e9,1e9,-1e9,1e9,-dep[u],dp[u]);
for(auto [v,w] : adj[u]) if(v != pa){
dep[v] = dep[u]+w;
dfs(v,u,nxt);
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 0; i < n-1; i++){
int a,b,c; cin >> a >> b >> c;
adj[a].emplace_back(b,c); adj[b].emplace_back(a,c);
}
for(int i = 2; i <= n; i++){
cin >> p[i] >> s[i];
}
dfs(1,0,nullptr);
for(int i = 2; i <= n; i++) cout << dp[i] << " \n"[i==n];
}
Compilation message
harbingers.cpp: In function 'node_t* upd(node_t*, int, int, int, int, func_t)':
harbingers.cpp:21:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
21 | int M = L + (R - L >> 1);
| ~~^~~
harbingers.cpp: In function 'num_t query(node_t*, int, int, int)':
harbingers.cpp:65:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | res = min(res, query(p->l, i, L, L + R >> 1));
| ~~^~~
harbingers.cpp:66:42: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | res = min(res, query(p->r, i, (L + R >> 1) + 1, R));
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3660 KB |
Output is correct |
| 3 |
Runtime error |
69 ms |
37536 KB |
Memory limit exceeded |
| 4 |
Runtime error |
113 ms |
65540 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
97 ms |
34564 KB |
Memory limit exceeded |
| 6 |
Correct |
116 ms |
32568 KB |
Output is correct |
| 7 |
Correct |
81 ms |
29736 KB |
Output is correct |
| 8 |
Runtime error |
138 ms |
65540 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
131 ms |
65540 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
117 ms |
65540 KB |
Execution killed with signal 9 |
