230718B3-path 题解

感谢 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

有几个地方要注意：

1. 边上有权而不是点，可以把权值转移到深度较深的点上，计算的时候注意 lca 对应的权值不算

2. 有多个询问，可以离线下来，按u排序，这样每次只需要修改跟上次不一样的点（按v排序），把操作次数降到 $O(n)$。

3. 起点和终点重合的情况最好加个特判

4. 记得开 long long

流程：

1. 输入，建边

2. dfs 找环+树剖

3. 建线段树

4. 询问排序，点排序

5. 每次修改线段树，计算答案

这题代码长达 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