BZOJ 3672 [NOI2014]购票 (凸优化+树剖/树分治)

  1 #include <map>
  2 #include <queue>
  3 #include <vector>
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <algorithm>
  7 #define N1 201000
  8 #define ll long long
  9 #define dd double
 10 #define inf 23333333333333333ll
 11 #define it map<node,int>::iterator
 12 using namespace std;
 13 
 14 int gint()
 15 {
 16     int ret=0,fh=1;char c=getchar();
 17     while(c<‘0‘||c>‘9‘){if(c==‘-‘)fh=-1;c=getchar();}
 18     while(c>=‘0‘&&c<=‘9‘){ret=ret*10+c-‘0‘;c=getchar();}
 19     return ret*fh;
 20 }
 21 int n,T;
 22 struct Edge{
 23 int to[N1<<1],nxt[N1<<1],head[N1],cte;ll val[N1<<1];
 24 void ae(int u,int v,ll w)
 25 {
 26     cte++;to[cte]=v,val[cte]=w;
 27     nxt[cte]=head[u],head[u]=cte;
 28 }
 29 }e;
 30 struct SEG{
 31 int cvh[21][N1];
 32 int TP[N1<<2]; ll *X,*Y;
 33 void build(int l,int r,int rt,int dep)
 34 {
 35     TP[rt]=l-1;
 36     if(l==r) return;
 37     int mid=(l+r)>>1;
 38     build(l,mid,rt<<1,dep+1);
 39     build(mid+1,r,rt<<1|1,dep+1);
 40 }
 41 void push(int *c,int l,int &tp,int id)
 42 {
 43     while(tp>l&&(1.0*Y[id]-1.0*Y[c[tp-1]])/(1.0*X[id]-1.0*X[c[tp-1]])<=(1.0*Y[c[tp]]-1.0*Y[c[tp-1]])/(1.0*X[c[tp]]-1.0*X[c[tp-1]]))
 44         tp--;
 45     c[++tp]=id;
 46 }
 47 ll cut(int *c,int l,int &tp,ll K)
 48 {
 49     if(tp<l) return inf;
 50     if(l==tp) return Y[c[tp]]-K*X[c[tp]];
 51     int r=tp,ans=l,mid; l++;
 52     while(l<=r)
 53     {
 54         mid=(l+r)>>1;
 55         if((1.0*Y[c[mid]]-1.0*Y[c[mid-1]])/(1.0*X[c[mid]]-1.0*X[c[mid-1]])<=1.0*K) ans=mid,l=mid+1;
 56         else r=mid-1;
 57     }
 58     return Y[c[ans]]-K*X[c[ans]];
 59 }
 60 void update(int x,int l,int r,int rt,int id,int dep)
 61 {
 62     push(cvh[dep],l,TP[rt],id);
 63     if(l==r) return; int mid=(l+r)>>1;
 64     if(x<=mid) update(x,l,mid,rt<<1,id,dep+1);
 65     else update(x,mid+1,r,rt<<1|1,id,dep+1);
 66 }
 67 ll query(int L,int R,int l,int r,int rt,ll K,int dep)
 68 {
 69     if(L<=l&&r<=R) return cut(cvh[dep],l,TP[rt],K);
 70     int mid=(l+r)>>1; ll ans=inf;
 71     if(L<=mid) ans=min(ans,query(L,R,l,mid,rt<<1,K,dep+1));
 72     if(R>mid) ans=min(ans,query(L,R,mid+1,r,rt<<1|1,K,dep+1));
 73     return ans;
 74 }
 75 }s;
 76 
 77 ll P[N1],Q[N1],L[N1],f[N1],dis[N1];
 78 int lg[N1];
 79 namespace tr{
 80 int st[N1],ed[N1],id[N1],tot,ff[N1][21];
 81 int dep[N1],fa[N1],tp[N1],son[N1],sz[N1];
 82 void dfs1(int u,int dad)
 83 {
 84     sz[u]=1; ff[u][0]=u;
 85     for(int j=e.head[u];j;j=e.nxt[j])
 86     {
 87         int v=e.to[j]; if(v==dad) continue;
 88         dis[v]=dis[u]+e.val[j]; dep[v]=dep[u]+1; 
 89         fa[v]=u; ff[v][1]=u; dfs1(v,u); 
 90         sz[u]+=sz[v]; if(sz[v]>sz[son[u]]) son[u]=v;
 91     }
 92 }
 93 void dfs2(int u)
 94 {
 95     st[u]=++tot; id[tot]=u; 
 96     if(son[u]) tp[son[u]]=tp[u],dfs2(son[u]);
 97     for(int j=e.head[u];j;j=e.nxt[j])
 98     {
 99         int v=e.to[j];
100         if(v==fa[u]||v==son[u]) continue;
101         tp[v]=v; dfs2(v);
102     }
103     ed[u]=tot;
104 }
105 void init()
106 {
107     int i,j; s.build(1,n,1,0);
108     s.X=dis,s.Y=f; s.update(1,1,n,1,1,0);
109     dfs1(1,-1); tp[1]=1; dfs2(1); 
110     for(j=2;j<=lg[n]+1;j++)
111         for(i=1;i<=n;i++) 
112             ff[i][j]=ff[ ff[i][j-1] ][j-1];
113 }
114 void solve(int x)
115 {
116     int y=x,j,z; f[x]=inf;
117     while(dis[x]-dis[tp[y]]<=L[x]&&y)
118         f[x]=min(f[x],s.query(st[tp[y]],st[y],1,n,1,P[x],0)),y=fa[tp[y]];
119     if(y&&dis[x]-dis[y]<=L[x])
120     {
121         for(z=y,j=lg[dep[y]]+1;j>=0;j--)
122             if(dis[x]-dis[ff[z][j]]<=L[x]) z=ff[z][j];
123         f[x]=min(f[x],s.query(st[z],st[y],1,n,1,P[x],0));
124     }
125     f[x]+=dis[x]*P[x]+Q[x];
126     s.update(st[x],1,n,1,x,0);
127 }
128 };
129 
130 int id[N1];
131 int cmp(int x,int y){return dis[x]<dis[y];}
132 
133 int main()
134 {
135     //freopen("t2.in","r",stdin);
136     freopen("testdata.in","r",stdin);
137     int i,x; ll w;
138     scanf("%d%d",&n,&T);
139     for(lg[1]=0,i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
140     for(id[1]=1,i=2;i<=n;i++)
141     {
142         scanf("%d%lld%lld%lld%lld",&x,&w,&P[i],&Q[i],&L[i]);
143         e.ae(x,i,w); id[i]=i; //e.ae(i,x,w); 
144     }
145     tr::init();
146     sort(id+1,id+n+1,cmp); 
147     for(i=2;i<=n;i++)
148         tr::solve(id[i]);
149     for(i=2;i<=n;i++)
150         printf("%lld\n",f[i]);
151     return 0;
152 }