//#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
long long inf=1e18,kaf=(1<<16),sor,makh;
struct func{
func(){
fas=shib=0;
}
long long fas;
int shib;
int inersect(func f){
sor=fas-f.fas,makh=f.shib-shib;
if(makh==0){
if(sor>0){
return -1;
}
return inf;
}
if(makh<0){
makh*=-1;
sor*=-1;
}
if(sor<0){
return -1;
}
return min((sor+makh-1)/makh,1000000000ll+3);
}
bool operator <(const func f)const {
return shib<f.shib;
}
}fakefunc,fp[maxn];
int p;
long long taf;
struct cht{
vector<pair<int,func*>>st;
void add(func *f){
while((int)st.size()>0){
taf=(*f).inersect(*st.back().second);
if(taf>1e9+10){
return ;
}
if(taf<=st.back().first){
st.pop_back();
continue;
}else{
st.emplace_back(make_pair(taf,f));
break;
}
}
if((int)st.size()==0){
st.emplace_back(make_pair(-1,f));
}
}
long long get(int x){
p=lower_bound(st.begin(),st.end(),make_pair(x+1,&fakefunc))-st.begin()-1;
if(p<0){
return -inf;
}
return (*st[p].second).fas+1ll*x*(*st[p].second).shib;
}
};
long long ret;
int m;
struct segment{
cht ch[(1<<17)];
void upd(int i,int l,int r,int tl,int tr,func* f){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
ch[i].add(f);
return ;
}
m=(l+r)>>1;
upd((i<<1),l,m,tl,tr,f);
m=(l+r)>>1;
upd((i<<1)^1,m+1,r,tl,tr,f);
}
void pors(int x,int v){
ret=-inf;
x+=kaf;
while(x>0){
ret=max(ret,ch[x].get(v));
x>>=1;
}
}
void clear(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
ch[i].st.clear();
ch[i].st.shrink_to_fit();
return ;
}
m=(l+r)>>1;
clear((i<<1),l,m,tl,tr);
m=(l+r)>>1;
clear((i<<1)^1,m+1,r,tl,tr);
}
}seg;
struct yal{
int u,v,w;
int getad(int fu){
return (u^v^fu);
}
}alle[maxn];
int n,timea=-1,high[maxn];
long long dp[maxn];
pair<int,int>stf[maxn],all[maxn];
vector<int>adj[maxn];
void dfs(int u,int par=0,int len=0){
if((int)adj[u].size()==1&&u!=1){
timea++;
stf[u].first=timea;
}else{
stf[u].first=timea+1;
}
high[u]=len;
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v!=par){
dfs(v,u,len+alle[x].w);
}
}
stf[u].second=timea;
}
void vorod(){
cin>>n;
for(int i=0;i<n-1;i++){
cin>>alle[i].u>>alle[i].v>>alle[i].w;
adj[alle[i].u].push_back(i);
adj[alle[i].v].push_back(i);
}
for(int i=2;i<=n;i++){
cin>>all[i].first>>all[i].second;
}
}
void pre(){
dfs(1);
}
void upd(int u){
seg.pors(stf[u].first,all[u].second);
dp[u]=1ll*min(-ret,0ll)+all[u].first+1ll*all[u].second*high[u];
fp[u].fas=-dp[u];
fp[u].shib=high[u];
seg.upd(1,0,kaf-1,stf[u].first,stf[u].second,&fp[u]);
}
void solve(int u=1,int para=0){
upd(u);
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v!=para){
solve(v,u);
}
}
seg.clear(1,0,kaf-1,stf[u].first,stf[u].second);
}
void khor(){
for(int i=2;i<=n;i++){
cout<<dp[i]<<" ";
}
cout<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
vorod();
pre();
solve();
khor();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11352 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
11612 KB |
Output isn't correct |
| 3 |
Incorrect |
37 ms |
16404 KB |
Output isn't correct |
| 4 |
Incorrect |
55 ms |
18648 KB |
Output isn't correct |
| 5 |
Incorrect |
72 ms |
20816 KB |
Output isn't correct |
| 6 |
Incorrect |
98 ms |
22868 KB |
Output isn't correct |
| 7 |
Incorrect |
60 ms |
16208 KB |
Output isn't correct |
| 8 |
Incorrect |
122 ms |
20772 KB |
Output isn't correct |
| 9 |
Runtime error |
143 ms |
34868 KB |
Memory limit exceeded |
| 10 |
Incorrect |
100 ms |
26064 KB |
Output isn't correct |
