제출 #434471

#제출 시각아이디문제언어결과실행 시간메모리
434471ScarletSHarbingers (CEOI09_harbingers)C++17
40 / 100
237 ms34640 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5+4; const ll INF = 1e18; int s[N], v[N]; ll dp[N]; vector<array<int,2>> e[N]; ll f(ll a, ll b, int x) { return a*x+b; } struct LiChao { struct node { ll a = 0, b = 0; node *l, *r; }; int n; node *root; deque<node> buffer; stack<node*> stk1; stack<array<ll,2>> stk2; stack<array<ll,2>> lines; node *newnode() { buffer.emplace_back(); return &buffer.back(); } LiChao(int n) : n(n) {root = newnode();} void update(node *&v, int l, int r, ll a, ll b, bool found) { if (!v) v=newnode(); int m=l+(r-l)/2; if (f(a,b,m)<f(v->a,v->b,m)) { swap(a,v->a); swap(b,v->b); if (!found) { found=1; stk1.top()=v; stk2.top()={a,b}; } } if (l==r) return; if (f(a,b,l)-f(v->a,v->b,l)<f(a,b,r)-f(v->a,v->b,r)) update(v->l,l,m,a,b,found); else update(v->r,m+1,r,a,b,found); } void update(ll a, ll b) { lines.push({a,b}); stk1.push(0); stk2.push({}); update(root,0,n,a,b,0); } ll query(node *v, int l, int r, int x) { if (x<l||r<x||!v) return INF; if (l==r) return f(v->a,v->b,x); int m=l+(r-l)/2; return min({f(v->a,v->b,x),query(v->l,l,m,x),query(v->r,m+1,r,x)}); } ll query(int x) { return query(root,0,n,x); } void rollback() { if (stk1.top()&&stk1.top()->a==lines.top()[0]&&stk1.top()->b==lines.top()[1]) { stk1.top()->a=stk2.top()[0]; stk1.top()->b=stk2.top()[1]; } stk1.pop(); stk2.pop(); lines.pop(); } }; LiChao lct(1e9); void dfs(int c, int p, int h) { dp[c]=1LL*v[c]*h+s[c]+lct.query(v[c]); lct.update(-h,dp[c]); for (auto i : e[c]) if (i[0]!=p) dfs(i[0],c,h+i[1]); lct.rollback(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n,x,y,z; cin>>n; for (int i=1;i<n;++i) { cin>>x>>y>>z; e[x].push_back({y,z}); e[y].push_back({x,z}); } for (int i=2;i<=n;++i) cin>>s[i]>>v[i]; dfs(1,0,0); for (int i=2;i<=n;++i) cout<<dp[i]<<" "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...