#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
struct line{
int m,n;
line(int m,int n):m(m),n(n){}
int operator()(int x) const{
return m*x+n;
}
};
struct node{
node *left,*right;
int L,R;
line lin;
node(int L,int R): L(L), R(R), left(nullptr), right(nullptr), lin(0, INF){}
};
int query(node* curr,int x){
if(curr==nullptr)return INF;
int mid = (curr->L+curr->R)/2;
if(mid==x)return curr->lin(x);
if(mid<x)return min(curr->lin(x), query(curr->right, x));
return min(curr->lin(x), query(curr->left, x));
}
void update(node* curr,line x, vector<pair<node*,node>> &updates){
int mid = (curr->L+curr->R)/2;
bool betterleft = curr->lin(curr->L) > x(curr->L);
bool betterright = curr->lin(curr->R) > x(curr->R);
bool bettermid = curr->lin(mid) > x(mid);
if(!(betterleft or bettermid or betterright))return;
if(bettermid and betterright and betterleft) {
updates.emplace_back(curr,*curr);
swap(x, curr->lin);
}
else if(betterleft and !bettermid){
if(curr->left==nullptr)curr->left = new node(curr->L,mid-1);
update(curr->left,x,updates);
} else if(!bettermid){
if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
update(curr->right,x,updates);
} else if(betterleft){
updates.emplace_back(curr,*curr);
swap(curr->lin,x);
if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
update(curr->right,x,updates);
} else {
updates.emplace_back(curr,*curr);
swap(curr->lin, x);
if(curr->left==nullptr)curr->left = new node(curr->L,mid-1);
update(curr->left,x,updates);
}
}
int DP[100001];
int S[100001];
int V[100001];
vector<pair<int,int>> adj[100001];
node* head = new node(1,1e9);
void dfs(int x,int p,int depth){
DP[x] = S[x]+V[x]*depth+ query(head,V[x]);
vector<pair<node*,node>> updates;
update(head,line(-depth,DP[x]),updates);
for(auto&i:adj[x])if(i.first!=p){
dfs(i.first,x,depth+i.second);
}
for(auto&i:updates)*i.first=i.second;
}
int32_t main(){
// freopen("harbingers.in","r",stdin);
// freopen("harbingers.out","w",stdout);
int n;
cin >> n;
for(int i=1;i<n;i++){
int u,v,d;cin>>u>>v>>d;
adj[u].emplace_back(v,d);
adj[v].emplace_back(u,d);
}
for(int i=2;i<=n;i++)cin>>S[i]>>V[i];
vector<pair<node*,node>> h;
update(head,line(0,0),h);
dfs(1,0,0);
for(int i=2;i<n;i++)cout<<DP[i]<<' ';
cout << DP[n] << '\n';
}
Compilation message
harbingers.cpp: In constructor 'node::node(long long int, long long int)':
harbingers.cpp:18:11: warning: 'node::R' will be initialized after [-Wreorder]
18 | int L,R;
| ^
harbingers.cpp:17:11: warning: 'node* node::left' [-Wreorder]
17 | node *left,*right;
| ^~~~
harbingers.cpp:20:5: warning: when initialized here [-Wreorder]
20 | node(int L,int R): L(L), R(R), left(nullptr), right(nullptr), lin(0, INF){}
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5980 KB |
Output is correct |
| 3 |
Runtime error |
89 ms |
44188 KB |
Memory limit exceeded |
| 4 |
Runtime error |
107 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
148 ms |
43160 KB |
Memory limit exceeded |
| 6 |
Runtime error |
160 ms |
37716 KB |
Memory limit exceeded |
| 7 |
Correct |
108 ms |
21876 KB |
Output is correct |
| 8 |
Runtime error |
153 ms |
65536 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
151 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
142 ms |
65536 KB |
Execution killed with signal 9 |
