#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int INF = 1e9 + 7;
const int maxn = 1e5 + 5;
vector<pll> adj[maxn];
int a[maxn], b[maxn], ans[maxn];
int n;
struct seg{
int m, k;
seg(){}
seg(int _m, int _k) : m(_m), k(_k){}
int operator ()(int x){
return m * x + k;
}
};
struct node{
int l, r;
seg ans;
// node() : l(0), r(0), ans(seg(0, 0)){}
// node(int m, int k) : l(0), r(0), ans(seg(m, k)){}
// node(seg _ans) : l(0), r(0), ans(_ans){}
} st[maxn * 10];
int cnt = 0;
int newnode(int x = 0){
int id = ++cnt;
st[id].l = st[x].l, st[id].r = st[x].r;
st[id].ans = st[x].ans;
return id;
}
int insert(seg cur, int nd, int l = 0, int r = INF){
if(!nd){
nd = newnode();
st[nd].ans = cur;
return nd;
}
nd = newnode(nd);
if(l == r){
if(st[nd].ans(l) > cur(l)) swap(st[nd].ans, cur);
return nd;
}
int m = (l + r) / 2;
if(st[nd].ans(m) > cur(m)) swap(st[nd].ans, cur);
if(st[nd].ans.m < cur.m) st[nd].l = insert(cur, st[nd].l, l, m);
else st[nd].r = insert(cur, st[nd].r, m + 1, r);
return nd;
}
int insert(int m, int k, int nd){ return insert(seg(m, k), nd);}
int qry(int pos, int nd, int l = 0, int r = INF){
if(!nd) return INF * INF;
if(l == r) return st[nd].ans(pos);
int m = (l + r) / 2;
if(pos <= m) return min(st[nd].ans(pos), qry(pos, st[nd].l, l, m));
else return min(st[nd].ans(pos), qry(pos, st[nd].r, m + 1, r));
}
int rt[maxn];
int dep[maxn];
void dfs(int pos, int prev){
if(pos){
ans[pos] = a[pos] + b[pos] * dep[pos] + qry(b[pos], rt[prev]);
}
rt[pos] = newnode(rt[prev]);
rt[pos] = insert(-dep[pos], ans[pos], rt[pos]);
for(auto [x, w] : adj[pos]){
if(x == prev) continue;
dep[x] = dep[pos] + w;
dfs(x, pos);
}
}
signed main(void){
fastio;
cin>>n;
for(int i = 0; i < n - 1; i++){
int a, b, w;
cin>>a>>b>>w;
a--, b--;
adj[a].eb(b, w);
adj[b].eb(a, w);
}
for(int i = 1; i < n; i++){
cin>>a[i]>>b[i];
}
dfs(0, -1);
for(int i = 1; i < n; i++) cout<<ans[i]<<" ";
cout<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10076 KB |
Output is correct |
| 3 |
Runtime error |
190 ms |
65536 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
167 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Execution timed out |
2201 ms |
65536 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2223 ms |
65536 KB |
Time limit exceeded |
| 7 |
Runtime error |
162 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Execution timed out |
2227 ms |
65536 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2332 ms |
65536 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2159 ms |
65536 KB |
Time limit exceeded |
