#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
long long inf=1e18,kaf=(1<<17);
struct func{
func(){
fas=shib=-inf;
}
long long fas,shib;
long long inersect(func f){
long long sor=fas-f.fas,makh=f.shib-shib;
if(makh==0){
if(sor>0){
return -inf;
}
return inf;
}
if(makh<0){
makh*=-1;
sor*=-1;
}
if(sor<0){
return sor/makh;
}
return (sor+makh-1)/makh;
}
bool operator <(const func f)const {
return shib<f.shib;
}
}fakefunc;
struct cht{
vector<pair<long long,func>>st;
void add(func f){
while((long long)st.size()>0){
long long x=f.inersect(st.back().second);
if(x<=st.back().first){
st.pop_back();
continue;
}else{
st.push_back(make_pair(x,f));
break;
}
}
if((long long)st.size()==0){
st.push_back(make_pair(-inf,f));
}
}
long long get(long long x){
long long p=lower_bound(st.begin(),st.end(),make_pair(x+1,fakefunc))-st.begin()-1;
if(p<0){
return -inf;
}
////cout<<st.back().second.fas<<" "<<st.back().second.shib<<" "<<st.back().first<<endl;
return st[p].second.fas+x*st[p].second.shib;
}
};
struct segment{
cht ch[(1<<18)];
void upd(long long i,long long l,long long r,long long tl,long long tr,func f){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
ch[i].add(f);
return ;
}
long long m=(l+r)>>1;
upd((i<<1),l,m,tl,tr,f);
upd((i<<1)^1,m+1,r,tl,tr,f);
}
long long pors(long long x,long long v){
long long ret=-inf;
x+=kaf;
while(x>0){
ret=max(ret,ch[x].get(v));
x>>=1;
}
return ret;
}
}seg;
struct yal{
long long u,v,w;
long long getad(long long fu){
return (u^v^fu);
}
}alle[maxn];
long long n,timea=0,high[maxn],para[maxn],dp[maxn];
pair<long long,long long>stf[maxn],all[maxn];
vector<long long>adj[maxn];
void dfs(long long u,long long par=0,long long len=0){
timea++;
para[u]=par;
high[u]=len;
stf[u].first=timea;
for(auto x:adj[u]){
long long v=alle[x].getad(u);
if(v!=par){
dfs(v,u,len+alle[x].w);
}
}
stf[u].second=timea;
}
void vorod(){
cin>>n;
for(long long 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(long long i=2;i<=n;i++){
cin>>all[i].first>>all[i].second;
}
}
void pre(){
dfs(1);
}
void upd(long long u){
dp[u]=min(-seg.pors(stf[u].first,all[u].second),0ll)+all[u].first+all[u].second*high[u];
func f;
f.fas=-dp[u];
f.shib=high[u];
seg.upd(1,0,kaf-1,stf[u].first,stf[u].second,f);
}
void solve(long long u=1){
upd(u);
for(auto x:adj[u]){
long long v=alle[x].getad(u);
if(v!=para[u]){
solve(v);
}
}
}
void khor(){
for(long long i=2;i<=n;i++){
cout<<dp[i]<<" ";
}
cout<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//cout.tie(0);
//freopen("inp.txt","r",stdin);
vorod();
pre();
solve();
khor();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
6 ms |
17188 KB |
Output is correct |
| 3 |
Correct |
71 ms |
24900 KB |
Output is correct |
| 4 |
Correct |
89 ms |
31672 KB |
Output is correct |
| 5 |
Correct |
107 ms |
30724 KB |
Output is correct |
| 6 |
Runtime error |
161 ms |
33364 KB |
Memory limit exceeded |
| 7 |
Correct |
85 ms |
26076 KB |
Output is correct |
| 8 |
Runtime error |
138 ms |
40908 KB |
Memory limit exceeded |
| 9 |
Runtime error |
145 ms |
48996 KB |
Memory limit exceeded |
| 10 |
Runtime error |
119 ms |
45652 KB |
Memory limit exceeded |
