P2305 [NOI2014] 购票题解

liuziqin · 2025-11-17 19:21:25 · 题解

提供一种题解区中没有的做法。

首先式子非常简单

f_{u}=\min_{v \in fa_u,d_u-d_v \le l_u} f_v+(d_u-d_v)p_u+q_u \\=-p_ud_v+f_v+d_up_u+q_u

在链上且没有 l_u 的限制就是李超线段树的板子题。

如果说放在树上，不考虑 l_u 的限制，我们可以用可撤销李超维护，在离开节点 u 时撤销在该点的线段即可。

现在加上 l_u 的限制，结合之前的算法，考虑线段树套可撤销李超线段树。

我们每次在外层线段树 dep_u 的位置插入一条线段，在 \log n 棵李超线段树上进行修改，查询时找出合法的深度区间，最后在退出 dfs 时进行撤销操作即可。

::::info[卡常小技巧]

把线段放李超外面存储，可以节省不少空间。
把 stack 改为手写邻接表，减少 STL 空间常数。
最后一次退出循环时不进行撤销操作。

快读快写。 ::::

#include<bits/stdc++.h>
#define ll long long
#define il inline 
#define re register
using namespace std;
inline char gc(){
static char buf[1<<20],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<< 20,stdin),p1==p2)?EOF:*p1++;
}
inline void read(ll &n){
bool w=0;
char c=gc();
for(;c<48||c>57;c=gc())
    w=c==45;
for(n=0;c>=48&&c<=57;c=gc())
    n=n*10+c-48;
n=w?-n:n;
}
char buf[1<<21];
int p1=-1;
const int p2=(1<<21)-1;
inline void flush(){fwrite(buf,1,p1+1,stdout); p1=-1;}
inline void pc(const char &x){if(p1==p2) flush(); buf[++ p1]=x;}
inline void write(ll x,char a){
if(x<0)pc(45),x=-x;
char c[21],s=0;
for(;x;)c[s++]=x%10,x/=10;
if(!s)pc(48);
for(;s--;)pc(c[s]+48);
pc(a);
}
const int N=200005;
const ll INF=1e18;
const int nn=1000000;
struct edge{
int to,nxt;
ll w;
}e[N<<1];
int head[N],cur;
il void add_edge(int u,int v,ll w){
e[++cur].to=v;
e[cur].nxt=head[u];
e[cur].w=w;
head[u]=cur;
}
struct line{
ll k,b;
int id;
il ll calc(ll x){
    return k*x+b;
}
};
il bool operator ==(line a,line b){
return a.k==b.k&&a.b==b.b&&a.id==b.id;
}
line sum[N];
struct segtree{
int ls[N*100],rs[N*100],cnt;
int top1[N*100],nxt1[N*100],id1[N*100],tot1;
int top2[N*100],nxt2[N*100],id2[N*100],tot2;
il void update(int &p,int l,int r,int x){
    if(!p){
        p=++cnt;
        id1[++tot1]=x;
        top1[p]=tot1;
        return ;
    }
    int ud=id1[top1[p]];
    if(!top1[p]||sum[x].calc(l)<=sum[ud].calc(l)&&sum[x].calc(r)<=sum[ud].calc(r)){
        id1[++tot1]=x;
        nxt1[tot1]=top1[p];
        top1[p]=tot1;
        return ;
    }
    if(top1[p]&&sum[x].calc(l)>=sum[ud].calc(l)&&sum[x].calc(r)>=sum[ud].calc(r)){
        id2[++tot2]=x;
        nxt2[tot2]=top2[p];
        top2[p]=tot2;
        return ;
    }
    int mid=(l+r)>>1;
    update(ls[p],l,mid,x);
    update(rs[p],mid+1,r,x);
}
il ll query(int p,int l,int r,int x){
    if(!p)return INF;
    int ud=id1[top1[p]];
    ll ans=sum[ud].calc(x);
    if(!top1[p])ans=INF;
    if(l==r)return ans;
    int mid=(l+r)>>1;
    if(mid>=x)return min(ans,query(ls[p],l,mid,x));
    else return min(ans,query(rs[p],mid+1,r,x));
}
il void del(int p,int l,int r,int x){
    if(!p)return ;
    if(top1[p]&&id1[top1[p]]==x){
        top1[p]=nxt1[top1[p]];
        return ;
    }
    if(top2[p]&&id2[top2[p]]==x){
        top2[p]=nxt2[top2[p]];
        return ;
    }
    int mid=(l+r)>>1;
    del(ls[p],l,mid,x);
    del(rs[p],mid+1,r,x);
}
}st;
struct segtree_to_segtree{
int rt[N<<2];
il void update(int p,int l,int r,int x,int v){
    st.update(rt[p],0,nn,v);
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(mid>=x)update(p*2,l,mid,x,v);
    else update(p*2+1,mid+1,r,x,v);
}
il void del(int p,int l,int r,int x,int v){
    st.del(rt[p],0,nn,v);
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(mid>=x)del(p*2,l,mid,x,v);
    else del(p*2+1,mid+1,r,x,v);
}
il ll query(int p,int l,int r,int x,int y,int tx){
    if(l>=x&&r<=y)return st.query(rt[p],0,nn,tx);
    int mid=(l+r)>>1;
    ll ans=INF;
    if(mid>=x)ans=min(ans,query(p*2,l,mid,x,y,tx));
    if(mid<y)ans=min(ans,query(p*2+1,mid+1,r,x,y,tx));
    return ans;
}
}st2;
ll p[N],q[N],l[N],n,dis[N],dp[N],crr;
int dep[N],fa[N][25],last[N],mx;
il void dfs0(int u,int f){
dep[u]=dep[f]+1;
fa[u][0]=f;
last[u]=u;
mx=max(mx,dep[u]);
for(re int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(re int i=20;i>=0;i--)
    if(dis[u]-dis[fa[last[u]][i]]<=l[u]&&fa[last[u]][i])last[u]=fa[last[u]][i];
for(re int i=head[u];i;i=e[i].nxt){
    int v=e[i].to,w=e[i].w;
    if(v==f)continue;
    dis[v]=dis[u]+w;
    dfs0(v,u);
}
}
il void dfs1(int u,int fa){
crr++;
if(u==1){
    dp[u]=0;
    sum[u]={0,0,1};
    st2.update(1,1,mx,1,1);
}
else{
    dp[u]=st2.query(1,1,mx,dep[last[u]],dep[u],p[u])+dis[u]*p[u]+q[u];
    sum[u]={-dis[u],dp[u],u};
    st2.update(1,1,mx,dep[u],u);
}
for(re int i=head[u];i;i=e[i].nxt){
    int v=e[i].to;
    if(v==fa)continue;
    dfs1(v,u);
}
if(crr<n)st2.del(1,1,mx,dep[u],u);
}
signed main(){
ll _;
read(n),read(_);
for(int i=2;i<=n;i++){
    ll v,w;
    read(v),read(w),read(p[i]),read(q[i]),read(l[i]);
    add_edge(v,i,w);
    add_edge(i,v,w);
}
dfs0(1,0);
dfs1(1,0);
for(re int i=2;i<=n;i++)write(dp[i],'\n');
flush();
}

P2305 [NOI2014] 购票 题解

P2305 [NOI2014] 购票题解