#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
const ll INFLL=1e18+7;
const int INF=1e9+7;
#define pb push_back
struct line{
ll a,b;
ll operator()(ll x){return a*x+b;}
};
struct node{
node *left_node=nullptr,*right_node=nullptr;
line l;
node(line x){l=x;}
};
struct rollback{
int idx;
node *where;
bool side;
line pre_val;
bool oper_type;
void make_rollback(){
if(oper_type){
if(!side){
delete where->left_node;
where->left_node=nullptr;
}else{
delete where->right_node;
where->right_node=nullptr;
}
}else{
where->l=pre_val;
}
}
};
int curr;
vector<rollback> rollbacks;
void update(node *v,int start,int end,line x){
if(v->l(start)<x(start)&&v->l(end)<x(end)) return;
if(v->l(start)>x(start)&&v->l(end)>x(end)){rollbacks.pb({curr,v,0,v->l,0}); v->l=x; return;}
int mid=(start+end)>>1;
if(v->l(mid)>x(mid)){
rollbacks.pb({curr,v,0,v->l,0});
swap(v->l,x);
}
if(v->l(start)>x(start)){
if(v->left_node==nullptr){rollbacks.pb({curr,v,0,{0,0},1}); v->left_node=new node(x);}
else update(v->left_node,start,mid,x);
}else{
if(v->right_node==nullptr){rollbacks.pb({curr,v,1,{0,0},1}); v->right_node=new node(x);}
else update(v->right_node,mid+1,end,x);
}
}
ll query(node *v,int start,int end,int x){
if(v==nullptr) return INFLL*5;
if(start==end) return v->l(x);
int mid=(start+end)>>1;
if(x<=mid) return min(v->l(x),query(v->left_node,start,mid,x));
else return min(v->l(x),query(v->right_node,mid+1,end,x));
}
node *root=new node({0,0});
void update(line x){++curr; update(root,-INF,INF,x);}
ll query(ll x){return query(root,-INF,INF,x);}
const int MAXN=1e5+7;
line arr[MAXN];
vector<pii> G[MAXN];
ll depth[MAXN];
ll dp[MAXN];
int preorder[MAXN];
int idx;
void DFS(int x,int pre,int dist){
preorder[x]=++idx;
depth[x]=depth[pre]+dist;
//enter
if(x!=1){
ll tmp=arr[x].b+arr[x].a*depth[x];
tmp+=query(arr[x].a);
dp[x]=tmp;
update({-depth[x],dp[x]});
}
for(pii v:G[x]) if(v.first!=pre) DFS(v.first,x,v.second);
//exit
if(x!=1){
while(!rollbacks.empty()&&rollbacks.back().idx==preorder[x]-1){
rollbacks.back().make_rollback();
rollbacks.pop_back();
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
int n; cin>>n;
for(int i=1;i<n;++i){
int a,b,c; cin>>a>>b>>c;
G[a].pb({b,c});
G[b].pb({a,c});
}
for(int i=2;i<=n;++i){
int a,b; cin>>a>>b;
arr[i]={b,a};
}
DFS(1,1,0);
for(int i=2;i<=n;++i) cout<<dp[i]<<" ";
cout<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3792 KB |
Output is correct |
| 3 |
Correct |
63 ms |
31684 KB |
Output is correct |
| 4 |
Runtime error |
115 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
105 ms |
36464 KB |
Memory limit exceeded |
| 6 |
Correct |
107 ms |
28140 KB |
Output is correct |
| 7 |
Correct |
87 ms |
21416 KB |
Output is correct |
| 8 |
Runtime error |
159 ms |
61368 KB |
Memory limit exceeded |
| 9 |
Runtime error |
135 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
167 ms |
63156 KB |
Memory limit exceeded |
