BZOJ_3672_ [Noi2014]购票_CDQ分治+斜率优化

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define N 200050
typedef double f2;
int head[N],to[N],nxt[N],fa[N],n,cnt,mx[N],tot,root,siz[N],S[N],top,vis[N];
ll val[N],dep[N],P[N],Q[N],L[N],f[N];
int a[N],b[N],la,lb;
inline void add(int u,int v,ll w) {
    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
bool cmp1(const int &x,const int &y) {
    return dep[x]-L[x]>dep[y]-L[y];
}
f2 K(int i,int j) {
    return (f2(f[i]-f[j]))/(dep[i]-dep[j]);
}
void dfs(int x) {
    int i; siz[x]=1;
    for(i=head[x];i;i=nxt[i]) {
        dep[to[i]]=dep[x]+val[i];
        dfs(to[i]);
        siz[x]+=siz[to[i]];
    }
}
void get_root(int x) {
    int i;
    siz[x]=1; mx[x]=0;
    for(i=head[x];i;i=nxt[i]) if(!vis[to[i]]) {
        get_root(to[i]);
        siz[x]+=siz[to[i]];
        mx[x]=max(mx[x],siz[to[i]]);
    }
    mx[x]=max(mx[x],tot-siz[x]);
    if(mx[root]>mx[x]) root=x;
}
void diu1(int x,int y) {
    int p;
    for(p=x;p!=fa[y];p=fa[p]) a[++la]=p;
}
void diu2(int x) {
    int i; b[++lb]=x;
    for(i=head[x];i;i=nxt[i]) if(!vis[to[i]]) {
        diu2(to[i]);
    }
}
void solve(int x) {
    tot=siz[x]; root=0; get_root(x); int rt=root; vis[rt]=1;
    //printf("%d %d\n",x,rt);
    if(x!=rt) siz[x]-=siz[rt],solve(x);
    la=lb=0;
    int i,j;
    diu1(rt,x);
    for(i=head[rt];i;i=nxt[i]) if(!vis[to[i]]) {
        diu2(to[i]);
    }//printf("%d %d\n",la,lb);
    for(i=2;i<=la;i++) if(dep[rt]-dep[a[i]]<=L[rt]) f[rt]=min(f[rt],f[a[i]]+(dep[rt]-dep[a[i]])*P[rt]+Q[rt]);
     
    sort(b+1,b+lb+1,cmp1);
     
    top=0,S[0]=0;
    for(j=1,i=1;i<=lb;i++) {
        int u=b[i];
        while(j<=la&&dep[u]-dep[a[j]]<=L[u]) {
            while(top>1&&K(S[top],a[j])>K(S[top-1],S[top])) top--;
            S[++top]=a[j++];
        }
        if(!top) continue;
        if(top==1) f[u]=min(f[u],f[S[1]]+(dep[u]-dep[S[1]])*P[u]+Q[u]);
        else {
            int l=1,r=top;
            while(l<r) {
                int mid=(l+r)>>1;
                if(P[u]>K(S[mid],S[mid+1])) r=mid;
                else l=mid+1;
            }
            f[u]=min(f[u],f[S[l]]+(dep[u]-dep[S[l]])*P[u]+Q[u]);
        }
    }
 
    for(i=head[rt];i;i=nxt[i]) if(!vis[to[i]]) {
        solve(to[i]);
    }
}
int main() {
    mx[0]=1<<30;
    scanf("%d%*d",&n);
    int i;
    ll x;
    for(i=2;i<=n;i++) {
        scanf("%d%lld%lld%lld%lld",&fa[i],&x,&P[i],&Q[i],&L[i]); add(fa[i],i,x);
    }
    memset(f,0x3f,sizeof(f));
    f[1]=0;
    dfs(1);
    solve(1);
    for(i=2;i<=n;i++) printf("%lld\n",f[i]);
}