经过不懈（抄题解）努力之后，终于AC了此题。
说起来很简单。
考虑一个链上的情况，
建立直角坐标系。
横坐标是t，纵坐标是距离链开头的距离d
m个路径就是一个线段
那么能碰撞，当且仅当线段有交。
给一些线段的集合，求两两之间的第一个交点。
做法：
扫描线。
set维护线段，按照纵坐标递增，纵坐标相同按斜率递增。用全局变量X重载小于号。
加入一个线段时候，把它和它的前驱后继求交。
删除一个线段时候，把它的后继和它的前驱求交。
交点横坐标贡献给答案。
虽然不能求出前多少大的交点，甚至两条线在相交之后相对位置会改变
但是无所谓！在第一个交点出现之前，两两线段的相对顺序不变
我们只需要第一个交点。之后的操作如果横坐标大于ans，直接break！
上面求的交点一定可以得到第一个交点（自己画画图）
树上？树链剖分，直接放到直上直下的链上去做！！！！
利用树剖logn段，经典套路
实现方式：
1.注意重链头上的边归给自己。
2.线段的存储方式：
如果直接写成k*x+b的形式，b会很大，产生精度误差。而且点点相交的时候也比较麻烦。
所以采用物理方式
记录到达这个链时候的开始时间，开始位置，结束位置，速度
求交点就是相遇问题。
求横坐标为X位置的值，也是用：位移=速度*时间
eps开的是1e-9
O(nlog^2n)很不满。
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);} template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Modulo{ const int mod=998244353; il int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;} il int sub(int x,int y){return ad(x,mod-y);} il int mul(int x,int y){return (ll)x*y%mod;} il void inc(int &x,int y){x=ad(x,y);} il void inc2(int &x,int y){x=mul(x,y);} il int qm(int x,int y=mod-2){int ret=1;while(y){if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;} template<class ...Args>il int ad(const int a,const int b,const Args &...args) {return ad(ad(a,b),args...);} template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);} } namespace Miracle{ const int N=1e5+5; const double inf=1e13; const double eps=1e-9; int n,m; struct node{ int nxt,to; }eg[2*N]; int hd[N],cnt; void add(int x,int y){ eg[++cnt].nxt=hd[x]; eg[cnt].to=y; hd[x]=cnt; } int dfn[N],df,top[N],fa[N],id[N]; int son[N],sz[N],dep[N]; ///////////////////////// double X;//here is X! ///////////////////////// int Fabs(double x){ if(x>eps) return 1; if(x<-eps) return -1; return 0; } struct line{ int st,nd; double bt,v; double friend operator &(line x,line y){ if(Fabs(x.v-y.v)){ double ny=y.st+(x.bt-y.bt)*y.v; double tim=x.bt+(ny-x.st)/(x.v-y.v); if(tim>y.bt-eps&&tim>x.bt-eps&&tim<y.bt+(y.nd-y.st)/y.v+eps&&tim<x.bt+(x.nd-x.st)/x.v+eps) return tim; return inf; }else{ if(Fabs((y.st-x.st)/x.v+x.bt-y.bt)==0) return max(y.bt,x.bt); return inf; } } bool friend operator <(line x,line y){ double nx=x.st+(X-x.bt)*x.v,ny=y.st+(X-y.bt)*y.v; if(Fabs(nx-ny)!=0) return nx<ny; if(Fabs(x.v-y.v)!=0) return x.v<y.v; if(x.st!=y.st) return x.st<y.st; return x.nd<y.nd; } }; struct hl{ vector<line>mem; int st,nd; }h[N]; int tot; void dfs(int x){ sz[x]=1; dep[x]=dep[fa[x]]+1; for(reg i=hd[x];i;i=eg[i].nxt){ int y=eg[i].to; if(y==fa[x]) continue; fa[y]=x; dfs(y); sz[x]+=sz[y]; if(sz[y]>sz[son[x]]) son[x]=y; } } void dfs2(int x){ dfn[x]=++df; if(!top[x]){ ++tot; if(x==1) h[tot].st=x; else h[tot].st=fa[x]; top[x]=x; id[x]=tot; h[tot].nd=x; }else{ id[x]=id[top[x]]; h[id[x]].nd=x; } if(son[x]) top[son[x]]=top[x],dfs2(son[x]); for(reg i=hd[x];i;i=eg[i].nxt){ int y=eg[i].to; if(y==fa[x]) continue; if(y==son[x]) continue; dfs2(y); } } int lca(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); x=fa[top[x]]; } if(dep[x]<dep[y]) swap(x,y); return y; } void push(int x,int y,int t,int c){ double xt=t; int anc=lca(x,y); int dis=dep[x]+dep[y]-2*dep[anc]; double yt=(double)t+(double)dis/c; while(top[x]!=top[y]){ if(dep[top[x]]>dep[top[y]]){//jump x int now=id[x]; line lp; lp.bt=xt; lp.st=dep[x]-dep[h[now].st]; lp.nd=0;lp.v=-c;h[now].mem.pb(lp); xt+=(double)(dep[x]-dep[h[now].st])/c; x=fa[top[x]]; }else{//jump y int now=id[y]; line lp; yt-=(double)(dep[y]-dep[h[now].st])/c; lp.bt=yt; lp.st=0;lp.nd=dep[y]-dep[h[now].st]; lp.v=c; h[now].mem.pb(lp); y=fa[top[y]]; } } if(dep[x]>dep[y]){ int now=id[x]; line lp; lp.bt=xt; lp.st=dep[x]-dep[h[now].st]; lp.nd=dep[y]-dep[h[now].st];lp.v=-c;h[now].mem.pb(lp); }else{ int now=id[y]; line lp; yt-=(double)(dep[y]-dep[x])/c; lp.bt=yt; lp.st=dep[x]-dep[h[now].st];lp.nd=dep[y]-dep[h[now].st]; lp.v=c; h[now].mem.pb(lp); } } double ans=inf; struct ev{ double p; int id,tp; bool friend operator <(ev a,ev b){ if(Fabs(a.p-b.p)!=0) return a.p<b.p; return a.tp>b.tp; } }e[2*N]; multiset<line>s; int main(){ rd(n);rd(m); int x,y; for(reg i=1;i<n;++i){ rd(x);rd(y); add(x,y); add(y,x); } dfs(1); dfs2(1); int t,c; for(reg i=1;i<=m;++i){ rd(t);rd(c);rd(x);rd(y); push(x,y,t,c); } ans=inf; for(reg i=1;i<=tot;++i){ int num=0; for(reg o=0;o<(int)h[i].mem.size();++o){ line lp=h[i].mem[o]; e[++num].id=o; e[num].p=lp.bt; e[num].tp=1; e[++num].id=o; e[num].p=lp.bt+(lp.nd-lp.st)/lp.v; e[num].tp=-1; } sort(e+1,e+num+1); s.clear(); for(reg j=1;j<=num;++j){ X=e[j].p; if(X>ans-eps) break; line lp=h[i].mem[e[j].id]; if(e[j].tp==1){ s.insert(lp); auto bc=s.lower_bound(lp); auto tmp=bc;++tmp; if(tmp!=s.end()){ ans=min(ans,(*tmp)&lp); } tmp=bc; if(tmp!=s.begin()){ --tmp; ans=min(ans,(*tmp)&lp); } }else{ auto bc=s.lower_bound(lp); if(bc!=s.end()){ if(bc!=s.begin()){ auto pr=bc;--pr; ans=min(ans,(*bc)&(*pr)); } } auto now=s.find(lp); s.erase(now); } } } if(ans>=inf-1) puts("-1"); else printf("%.10lf",ans); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */
两个知识点：
1.线段集合求最小的交点。
2.树链剖分，路径放到链上转化为序列问题。