#include <bits/stdc++.h>
//#define cin in
//#define cout out
#define ll long long int
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
using namespace std;
const ll inf=2e18;
ll dis=0;
int cont=0;
struct line{
ll m=1e9, b=1e9;
int id=0;
bool ex=false;
ll eval(ll x){
return (dis+m)*x+b;
}
bool operator==(line a)const{
return m==a.m && b==a.b && ex==a.ex;
}
};
const int lim=1e5+5;
line deleted[lim]{};
int n;
vector<pii> ady[lim];
pii harb[lim];
bool vis[lim]{};
ll dp[lim]{};
ifstream in;
ofstream out;
ll h=0;
struct lichao{
lichao *left=0, *right=0;
ll l, r, mid;
line act;
lichao(ll x, ll y){
l=x;
r=y;
mid=(l+r)/2ll;
}
void insert(line nw){
while(act.ex && !vis[act.id]) act=deleted[act.id];
if(!act.ex){
act=nw;
return;
}
if(act.eval(mid)>nw.eval(mid)) swap(act,nw);
if(l==r || act.m==nw.m){
deleted[act.id]=nw;
return;
}
if(act.m<nw.m){
if(!left) left=new lichao(l,mid);
left->insert(nw);
}else{
if(!right) right=new lichao(mid+1ll,r);
right->insert(nw);
}
}
ll query(ll x){
while(act.ex && !vis[act.id]) act=deleted[act.id];
if(r<x || x<l) return inf;
if(l==r){
if(act.ex) return act.eval(x);
else return inf;
}
ll ans=inf;
if(act.ex) ans=act.eval(x);
if(left) ans=min(ans,left->query(x));
if(right) ans=min(ans,right->query(x));
return ans;
}
};
lichao cht(0,2e9);
void dfs(int u){
vis[u]=true;
if(u>1){
dis=h;
dp[u]=harb[u].fi+cht.query(harb[u].se);
}
dis=0;
deleted[u].ex=false;
cht.insert({-h,dp[u],u,true});
for(pii v:ady[u]){
if(!vis[v.fi]){
h+=v.se;
dfs(v.fi);
h-=v.se;
}
}
vis[u]=false;
}
int main(){
in.open("harbingers.in");
out.open("harbingers.out");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int u, v;
ll w;
int n;
cin>>n;
for(int i=1; i<n; i++){
cin>>u>>v>>w;
ady[u].push_back({v,w});
ady[v].push_back({u,w});
}
for(int i=2; i<=n; i++){
cin>>harb[i].fi>>harb[i].se;
}
dfs(1);
for(int i=2; i<=n; i++){
cout<<dp[i]<<" ";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
3 ms |
3136 KB |
Output is correct |
3 |
Correct |
56 ms |
13352 KB |
Output is correct |
4 |
Correct |
76 ms |
17996 KB |
Output is correct |
5 |
Correct |
117 ms |
19704 KB |
Output is correct |
6 |
Correct |
121 ms |
23380 KB |
Output is correct |
7 |
Incorrect |
89 ms |
12072 KB |
Output isn't correct |
8 |
Correct |
99 ms |
19604 KB |
Output is correct |
9 |
Incorrect |
105 ms |
23356 KB |
Output isn't correct |
10 |
Incorrect |
101 ms |
21452 KB |
Output isn't correct |