#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<ll, ll>
#define ll long long
#define ld long double
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a: b)
using namespace std;
const int lim=1e5+5;
vector<pii> ady[lim];
bool vis[lim]{};
pii harb[lim];
ll dp[lim]{};
ll dis=0;
struct line{
ll m, b;
};
ll eval(line a, ll x){
return (dis+a.m)*x+a.b;
}
ld isec(line l1, line l2){
return (l1.b-l2.b)/(l2.m-l1.m);
}
deque<line> cht;
vector<line> deleted[lim];
ll solve(int u){
ll l=0, r=cht.size()-1, mid, x=(ll)harb[u].se;
while(l<=r){
mid=(l+r)/2;
if(mid==cht.size()-1 || isec(cht[mid],cht[mid+1])>=(ld)x) r=mid-1;
else l=mid+1;
}
return eval(cht[l],x)+(ll)harb[u].fi;
}
void dfs(int u){
vis[u]=true;
if(u>1) dp[u]=solve(u);
cht.push_back({-dis,dp[u]});
int sz=cht.size();
while(sz>2 && isec(cht[sz-1],cht[sz-2])<=isec(cht[sz-1],cht[sz-3])){
deleted[u].push_back(cht[sz-2]);
cht[sz-2]=cht[sz-1];
cht.pop_back();
sz--;
}
repa(v, ady[u]){
if(!vis[v.fi]){
dis+=v.se;
dfs(v.fi);
dis-=v.se;
}
}
cht.pop_back();
while(deleted[u].size()){
cht.push_back(deleted[u].back());
deleted[u].pop_back();
}
}
int main(){
ll u, v, w;
int n;
cin>>n;
rep(i,1,n){
cin>>u>>v>>w;
ady[u].push_back({v,w});
ady[v].push_back({u,w});
}
rep(i,2,n+1) cin>>harb[i].fi>>harb[i].se;
dfs(1);
rep(i,2,n+1) cout<<dp[i]<<" ";
cout<<endl;
}
Compilation message
harbingers.cpp: In function 'long long int solve(int)':
harbingers.cpp:38:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | if(mid==cht.size()-1 || isec(cht[mid],cht[mid+1])>=(ld)x) r=mid-1;
| ~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7516 KB |
Output is correct |
2 |
Correct |
4 ms |
8028 KB |
Output is correct |
3 |
Correct |
61 ms |
15456 KB |
Output is correct |
4 |
Incorrect |
83 ms |
19028 KB |
Output isn't correct |
5 |
Correct |
113 ms |
23012 KB |
Output is correct |
6 |
Incorrect |
138 ms |
26192 KB |
Output isn't correct |
7 |
Incorrect |
85 ms |
17288 KB |
Output isn't correct |
8 |
Runtime error |
196 ms |
65536 KB |
Execution killed with signal 9 |
9 |
Runtime error |
183 ms |
65536 KB |
Execution killed with signal 9 |
10 |
Runtime error |
184 ms |
65536 KB |
Execution killed with signal 9 |