题解：P11343 「KTSC 2023 R1」出租车旅行

· · 题解

参考了 https://qoj.ac/blog/znstz/blogs/680。

你搭乘出租车的过程是：从 0 号点坐出租车出发，到达另一个点，换乘出租车到达下一个点，直至终点。

由于出租车能走的距离是无限的，所以有一个显然的事实：对于所有你搭乘的出租车，其 B_i 关于你搭乘的顺序单调不增。

故将所有点的 B_i 从大到小排，令 f_i 表示到达点 i 所需的最小代价，转移就是

f_i=\min_{j|B_j>B_i}\{f_j+A_j+B_j\cdot \operatorname{dis}(i,j)\}

这个转移的问题是，终点的 B_i 不一定满足单调性，最后再转移一下就行了，即 ans_u=\min_{j}\{f_j+A_j+B_j\cdot \operatorname{dis}(u,j)\}。

直接转移可以做到 O\left(N^2\right)。

考虑优化。\operatorname{dis}(i,j) 的计算涉及到 LCA，不难想到点分树。

应用点分树时，先想一下普通点分治怎么转移。对于分治中心 u，考虑一个子树内的点 s 到另一个子树内的点 t 的转移，发现代价形式是关于 \operatorname{dis}(u,t) 的一次函数，不难想到李超树。

回到点分树上来，按 B_i 从大到小转移时，可以把转移代价记在所有祖先上，接受转移时查询所有祖先，这意味差要对每个点维护一棵李超树。

现在应该差不多了，梳理一下过程：

  1. 按 B_i 从大到小枚举转移点 u。
  2. 从 u 的每个点分树上的祖先查询最小代价，作为 f_u。
  3. 对 u 的每个点分树上的祖先更新最小代价。

一份 QOJ 上可过的代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}

std::vector<ll> travel(std::vector<ll> A, std::vector<int> B, std::vector<int> U,std::vector<int> _V, std::vector<int> W){
    const ll INF=1e18;
    int N=A.size();
    std::vector<std::vector<std::pair<int,int> > > G(N);
    std::vector<std::vector<std::pair<int,ll> > > cdv(N);
    std::vector<int> siz(N),vis(N);
    int Gc;
    auto dfsgc=[&](auto&&self,int x,int p,int als)->void{
        siz[x]=1;
        bool F=1;
        for(auto e:G[x]) if(e.fi!=p&&!vis[e.fi]){
            self(self,e.fi,x,als);
            siz[x]+=siz[e.fi];
            if(siz[e.fi]*2>als) F=0;
        }
        if(F&&(als-siz[x])*2<=als&&!Gc) Gc=x;
    };
    auto dfsval=[&](auto&&self,int x,int p,ll d,int s)->void{
        cdv[x].emplace_back(s,d);
        for(auto e:G[x]) if(!vis[e.fi]&&e.fi!=p) self(self,e.fi,x,d+e.se,s);
    };
    auto dfz=[&](auto&&self,int x,int als)->void{
        Gc=0;
        dfsgc(dfsgc,x,-1,als);
        x=Gc;
        vis[x]=1;
        dfsval(dfsval,x,-1,0,x);
        for(auto e:G[x]) if(!vis[e.fi]){
            int tsiz=siz[e.fi]>siz[x]?als-siz[x]:siz[e.fi];
            self(self,e.fi,tsiz);
        }
    };
    for(int i=0;i<N-1;++i){
        G[U[i]].emplace_back(_V[i],W[i]);
        G[_V[i]].emplace_back(U[i],W[i]);
    }

    struct LINE{
        ll k,b;
        LINE(ll a=-1,ll _b=0){
            k=a;
            b=_b;
        }ll operator()(ll x){
            return k==-1?INF:k*x+b;
        }
    };
    struct SEGN{
        LINE v;
        int l,r;
    };
    static SEGN tr[40000000];
    std::vector<int> rt(N);
    int trcnt=0;
    const ll V=1e12;
    auto trins=[&](auto&&self,int&x,ll l,ll r,LINE z)->void{
        if(z.k==-1||l==r) return;
        ll mid=l+r>>1;
        if(!x) x=++trcnt;
        if(z(mid)<tr[x].v(mid)) std::swap(tr[x].v,z);
        if(z.k==-1||l==r) return;
        if(z(l)<tr[x].v(l)) self(self,tr[x].l,l,mid,z);
        if(z(r)<tr[x].v(r)) self(self,tr[x].r,mid+1,r,z);
    };
    auto trque=[&](auto&&self,int x,ll l,ll r,ll p)->ll{
        ll ans=INF;
        if(!x) return ans;
        ans=tr[x].v(p);
        ll mid=l+r>>1;
        if(p<=mid) return min(ans,self(self,tr[x].l,l,mid,p));
        else return min(ans,self(self,tr[x].r,mid+1,r,p));
    };

    dfz(dfz,0,N);
    //for(int i=0;i<N;++i){
    //    printf("%d:",i);
    //    for(auto p:cdv[i]) printf("%d %lld|",p.fi,p.se);
    //    puts("");
    //}
    std::vector<int> pi(N);
    for(int i=0;i<N;++i) pi[i]=i;
    std::sort(pi.begin(),pi.end(),[&](int x,int y){return B[x]>B[y];});
    for(auto p:cdv[0]) trins(trins,rt[p.fi],0,V,LINE{B[0],A[0]+B[0]*p.se});
    for(int x:pi){
        ll val=INF;
        for(auto p:cdv[x]) cmin(val,trque(trque,rt[p.fi],0,V,p.se));
        for(auto p:cdv[x]) trins(trins,rt[p.fi],0,V,LINE{B[x],A[x]+val+B[x]*p.se});
    }
    std::vector<ll> ans(N-1);
    for(int x=1;x<N;++x){
        ans[x-1]=INF;
        for(auto p:cdv[x]) cmin(ans[x-1],trque(trque,rt[p.fi],0,V,p.se));
    }
    return ans;
}