#include <iostream>
#include <vector>
#include <queue>
#define ll long long
using namespace std;
struct triple{ll x, a, b;};
vector<ll> V[100500],D[105000];
vector<triple> S;
priority_queue<pair<ll, int>> pq;
ll a[100500], b[100500], xsum[100500];
ll ans[100500];
void dfs(int x){
for(int i=0; i<V[x].size(); i++){
if(xsum[V[x][i]]==0&&V[x][i]!=1){
xsum[V[x][i]] = xsum[x]+D[x][i];
dfs(V[x][i]);
}
}
}
int main() {
int n;
cin>>n;
for(int i=1; i<n; i++){
int x,y,d;
cin>>x>>y>>d;
V[x].push_back(y);
V[y].push_back(x);
D[x].push_back(d);
D[y].push_back(d);
}
for(int i=2; i<=n; i++) cin>>a[i]>>b[i];
dfs(1);
pq.push(make_pair(0, 1));
while(!pq.empty()){
ll val = pq.top().first;
int node = pq.top().second;
pq.pop();
while(!S.empty()&&S.back().x>=val) S.pop_back();
S.push_back(triple{val, -xsum[node], ans[node]});
for(int i=0; i<V[node].size(); i++){
if(ans[V[node][i]]==0&&V[node][i]!=1){
int s = 0;
int e = S.size()-1;
while(s!=e){
int m = (s+e)/2+1;
if(S[m].x<=b[V[node][i]]) s = m;
else e = m-1;
}
ans[V[node][i]] = a[V[node][i]]+b[V[node][i]]*(xsum[V[node][i]]+S[s].a)+S[s].b;
s = 0;
e = S.size()-1;
while(s!=e){
int m = (s+e)/2+1;
if(S[m].a*S[m].x+S[m].b<-xsum[V[node][i]]*S[m].x+ans[V[node][i]]) s = m;
else e = m-1;
}
ll x = (ans[V[node][i]]-S[s].b)/(xsum[V[node][i]]+S[s].a);
pq.push(make_pair(x+1, V[node][i]));
}
}
}
for(int i=2; i<=n; i++) cout<<ans[i]<<" ";
}
Compilation message
harbingers.cpp: In function 'void dfs(int)':
harbingers.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i=0; i<V[x].size(); i++){
| ~^~~~~~~~~~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0; i<V[node].size(); i++){
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5072 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5456 KB |
Output is correct |
| 3 |
Correct |
106 ms |
12936 KB |
Output is correct |
| 4 |
Correct |
158 ms |
16372 KB |
Output is correct |
| 5 |
Correct |
202 ms |
19308 KB |
Output is correct |
| 6 |
Correct |
272 ms |
22544 KB |
Output is correct |
| 7 |
Correct |
153 ms |
15528 KB |
Output is correct |
| 8 |
Correct |
273 ms |
22264 KB |
Output is correct |
| 9 |
Correct |
280 ms |
24024 KB |
Output is correct |
| 10 |
Correct |
246 ms |
22900 KB |
Output is correct |
