【230718 B3】path 题解

Cindy_Li · 2023-08-06 16:08:00 · 个人记录

感谢 cn_ryh 大佬的怂恿（否则我真不会动这个题

感谢 cszhpdx 的指导帮助 qwq

（让我们膜拜一下场切的浩杨哥 orz

解决这个题让人很有成就感（

题意

给定一个基环树，边有长度l、限速v、价值w（每单位时间）

已知起点s、终点t、最高速度u，求最小花费

边数、询问次数 10^5

解法

首先学习一下基环树，在这个题里环对答案的影响就是让路径多了一条。

考虑环上的任意一边，两条路径一定分别经过和不经过这条边。

不经过：断掉这条边，让基环树变成树。
强制经过：让起终点分别到两端点，再加上这条边本身。

现在问题转化为在树上求两点间路径，计算花费

~~众所不周知~~，树链剖分就是干这个用的

由于树剖保证同一条重链上dfs序连续，这很明显就是区间查询，所以可以在dfs序上建线段树等数据结构。

显然对于每条边，为了花费最小，要求时间最短，速度最大。只有 2 种情况：按照 v 跑和按照 u 跑（ V=\min(u,v) ）。

那么我们建两棵线段树，分别记录当前按v跑的总花费，按u跑的总花费，查询的时候加起来就好了（

大体的思路就是上面说的这样qwq

有几个地方要注意：

边上有权而不是点，可以把权值转移到深度较深的点上，计算的时候注意 lca 对应的权值不算
有多个询问，可以离线下来，按u排序，这样每次只需要修改跟上次不一样的点（按v排序），把操作次数降到 O(n)。
起点和终点重合的情况最好加个特判
记得开 long long

流程：

输入，建边
dfs 找环+树剖
建线段树
询问排序，点排序
每次修改线段树，计算答案

这题代码长达 5k，细节还是挺多的（尤其是点排序后很多下标会变化，要想清楚）

还是放一下完整代码纪念我写过最长的题qwq

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define rep0(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n;i>=1;i--)
#define REPG(i,h,x) for(int i=h[x];~i;i=e[i].next)
#define LL long long

inline int read(){
    int s=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) s=s*10+c-'0';
    return s*f;
}

const int N=1e5+50;

int head[N],cnt;
struct edge{
    int to,next,len,dj;
}e[2*N];
inline void add(int x,int y,int l,int dj){
    e[++cnt]=(edge){y,head[x],l,dj};head[x]=cnt;
}

int tot;
int rkp[N],rkd[N];

struct point{
    int fa,dep,siz,son;
    int len,dj;
    int top,dfn;
    int id;
    inline bool operator<(const point &a) const{
        return dj>a.dj;
    }
}p[N];

struct duan{
    int a,b,l,x;
}d;

inline void dfs_c(int u){
    p[u].son=-1;p[u].siz=1;
    REPG(i,head,u){
        int v=e[i].to;
        if(v==p[u].fa||(u==d.a&&v==d.b)) continue;
        if(p[v].dep){
            d.a=u,d.b=v;
            d.l=e[i].len,d.x=e[i].dj;
        }
        else{
            p[v].fa=u;
            p[v].dep=p[u].dep+1;
            p[v].len=e[i].len,p[v].dj=e[i].dj;
            dfs_c(v);
            p[u].siz+=p[v].siz;
            if(p[u].son==-1||p[v].siz>p[p[u].son].siz) p[u].son=v;
        }
    }
}

inline void dfs_p(int u,int t){
    p[u].top=t;
    p[u].dfn=++tot;
    rkd[tot]=u;
    if(p[u].son==-1) return;
    dfs_p(p[u].son,t);
    REPG(i,head,u){
        int v=e[i].to;
        if((u==d.a&&v==d.b)||(u==d.b&&v==d.a)) continue;
        if(v!=p[u].son&&v!=p[u].fa) dfs_p(v,v);
    }
}

struct SegmentTree{
    int cnt;
    int ls[2*N],rs[2*N];
    double sum[2*N];

    inline int build(int l,int r){
        int x=++cnt;sum[x]=0;
        if(l==r) return x;
        int mid=(l+r)>>1;
        ls[x]=build(l,mid);
        rs[x]=build(mid+1,r);
        return x;
    }

    inline void pushup(int x){
        sum[x]=sum[ls[x]]+sum[rs[x]];
    }
    inline void change(int x,int l,int r,int p,double v){
        if(l==r) return sum[x]=v,void();
        int mid=(l+r)>>1;
        if(mid>=p) change(ls[x],l,mid,p,v);
        else change(rs[x],mid+1,r,p,v);
        pushup(x);
    }

    inline double query(int x,int l,int r,int s,int t){
        if(l>=s&&r<=t) return sum[x];
        double res=0;
        int mid=(l+r)>>1;
        if(mid>=s) res+=query(ls[x],l,mid,s,t);
        if(t>mid) res+=query(rs[x],mid+1,r,s,t);
        return res;
    }
}t1,t2;

struct question{
    int s,t,u;
    int id;
    inline void rd(){
        s=read(),t=read(),u=read();
    }
    inline bool operator< (const question &a)const{
        return u<a.u;
    }
}q[N];
double ans[N];

int n,m,Q;
int v[N],w[N];

inline double dis(int x,int y,int u){
    if(x==y) return 0;
    double res=0;x=rkp[x],y=rkp[y];
    int fx=rkp[p[x].top],fy=rkp[p[y].top];
    while(fx!=fy){
        if(p[fx].dep>=p[fy].dep)
            res+=t1.query(1,1,n,p[fx].dfn,p[x].dfn)+t2.query(1,1,n,p[fx].dfn,p[x].dfn)/u,
            x=rkp[p[fx].fa];
        else
            res+=t1.query(1,1,n,p[fy].dfn,p[y].dfn)+t2.query(1,1,n,p[fy].dfn,p[y].dfn)/u,
            y=rkp[p[fy].fa];
        fx=rkp[p[x].top];fy=rkp[p[y].top];
    }
    if(p[x].dfn<p[y].dfn)
        res+=t1.query(1,1,n,p[rkp[p[x].son]].dfn,p[y].dfn)+t2.query(1,1,n,p[rkp[p[x].son]].dfn,p[y].dfn)/u;
    else
        res+=t1.query(1,1,n,p[rkp[p[y].son]].dfn,p[x].dfn)+t2.query(1,1,n,p[rkp[p[y].son]].dfn,p[x].dfn)/u;
    return res;
}

int main(){
    memset(head,-1,sizeof(head));
    n=read(),m=read(),Q=read();
    rep(i,n){
        int a,b,l,x;
        a=read(),b=read(),l=read(),x=read();
        add(a,b,l,x);
        add(b,a,l,x);
    }
    p[1].dep=1;dfs_c(1);
    dfs_p(1,1);

    rep(i,m){
        v[i]=read(),w[i]=read();
    }

    rep(i,Q){
        q[i].rd();
        q[i].id=i;
    }
    sort(q+1,q+Q+1);

    rep(i,n) p[i].id=i;
    sort(p+1,p+n+1);
    rep(i,n) rkp[p[i].id]=i;

    int rt=t1.build(1,n);
    rt=t2.build(1,n);
    rep(i,n){
        t2.change(rt,1,n,i,(LL)p[rkp[rkd[i]]].len*w[p[rkp[rkd[i]]].dj]);
    }
    int lst=1;
    rep(i,Q){
        int u=q[i].u;
        while(v[p[lst].dj]<u&&lst<=n){
            t1.change(rt,1,n,p[lst].dfn,(double)p[lst].len/v[p[lst].dj]*w[p[lst].dj]);
            t2.change(rt,1,n,p[lst].dfn,0);
            lst++;
        }
        double res=dis(q[i].s,q[i].t,u);
        res=min(res,dis(q[i].s,d.a,u)+dis(q[i].t,d.b,u)+(double)d.l/min(v[d.x],u)*w[d.x]);
        res=min(res,dis(q[i].s,d.b,u)+dis(q[i].t,d.a,u)+(double)d.l/min(v[d.x],u)*w[d.x]);
        ans[q[i].id]=res;
    }
    rep(i,Q) printf("%.2lf\n",ans[i]);
    return 0;
}

完结撒花 qwq