#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const long double EPS = 0.000001;
const int INF = 1e18+50;
const int N = 1e5+5;
const int ALPH = 26;
const int LGN = 25;
const int MOD = 1e9+7;
const int MAXR = 1e9+5;
int n;
struct Line {
int m,c;
Line() {
m = 0;
c = INF;
}
Line(int a, int b) {
m = a;
c = b;
}
int eval(int x) {
return m*x + c;
}
};
struct Node {
Node *lc, *rc;
Line data;
Node() {
lc = NULL;
rc = NULL;
data = Line();
}
Node(Line val) {
data = val;
lc = NULL;
rc = NULL;
}
void push() {
if(lc == NULL) lc = new Node();
if(rc == NULL) rc = new Node();
}
int query(int tl, int tr, int ind) {
if(tl == tr) {
return data.eval(ind);
}
push();
int tm = (tl + tr) / 2;
if(ind <= tm) {
return min( data.eval(ind), lc->query(tl, tm, ind) );
}
else {
return min( data.eval(ind), rc->query(tm+1, tr, ind) );
}
}
};
Node *update(Node *v, int tl, int tr, Line nw) {
if(tl == tr) {
if(v->data.eval(tl) > nw.eval(tl)) {
return new Node(nw);
}
else {
return new Node(*v);
}
}
v->push();
int tm = (tl + tr) / 2;
Node *ret = new Node(*v);
if(ret->data.m > nw.m) {
swap(ret->data , nw);
}
if(ret->data.eval(tm) > nw.eval(tm)) {
swap(nw, ret->data);
ret->rc = update(v->rc, tm+1, tr, nw);
}
else {
ret->lc = update(v->lc, tl, tm, nw);
}
return ret;
}
int harv[N], hars[N], path[N];
Node *roots[N];
vector<array<int,2> > adj[N];
int res[N];
void dfs(int node, int par) {
res[node] = harv[node] * path[node] + hars[node] + roots[par]->query(0, MAXR, harv[node]);
roots[node] = update(roots[par] , 0, MAXR, Line(-path[node], res[node]));
for(auto c : adj[node]) {
if(c[0] == par) continue;
path[c[0]] = c[1] + path[node];
dfs(c[0], node);
}
}
inline void solve() {
cin>>n;
for(int i = 0; i<n-1; i++) {
int u, v, d;
cin>>u>>v>>d;
adj[u].pb({v, d});
adj[v].pb({u, d});
}
for(int i = 2; i<=n; i++) {
cin>>hars[i]>>harv[i];
}
path[1] = 0;
roots[0] = new Node();
roots[0] = update(roots[0], 0, MAXR, Line(0, 0));
dfs(1, 0);
for(int i = 2; i<=n; i++) {
cout<<res[i]<<"\n";
}
}
signed main() {
fastio();
int test = 1;
//cin>>test;
while(test--) {
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
5 ms |
8712 KB |
Output is correct |
3 |
Runtime error |
71 ms |
65536 KB |
Execution killed with signal 9 |
4 |
Runtime error |
89 ms |
65536 KB |
Execution killed with signal 9 |
5 |
Runtime error |
93 ms |
65536 KB |
Execution killed with signal 9 |
6 |
Runtime error |
107 ms |
65536 KB |
Execution killed with signal 9 |
7 |
Runtime error |
81 ms |
65536 KB |
Execution killed with signal 9 |
8 |
Runtime error |
98 ms |
65536 KB |
Execution killed with signal 9 |
9 |
Runtime error |
94 ms |
65536 KB |
Execution killed with signal 9 |
10 |
Runtime error |
87 ms |
65536 KB |
Execution killed with signal 9 |