题目大意
一棵树上有m个人,每个人有出现时间、速度以及起点终点,到达终点时会瞬间消失,求最早两人相遇的时间
n,m<=1e5
题解
树剖变成若干线段求交,按照时间排序后set维护即可,相交的两个只可能相邻所以只用考虑相邻两个的
注意考虑k相等的情况
code
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define abs(x) ((x)>0?(x):-(x))
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define E 0.00000001
#define ll long long
//#define file
using namespace std;
struct Type{double x,X,k,b;int s;} c[300001];
vector<Type> b[100001];
int a[200001][2],ls[100001],d[100001],fa[100001][17],top[100001],nx[100001],sz[100001],n,m,i,j,k,l,len,x,y,Lca,tot;
double T,C,ans,sum,s1,s2,tt;
struct type{double x1,x2,k,b;};
bool operator < (type a,type b) {return a.k*tt+a.b<b.k*tt+b.b;}
set<type> st;
set<type> :: iterator I1,I2;
bool cmp(Type a,Type b) {return abs(a.x-b.x)>E && a.x<b.x || abs(a.x-b.x)<=E && a.s>b.s;}
void New(int x,int y) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;}
void dfs(int Fa,int t)
{
int i,mx=0;
sz[t]=1,d[t]=d[Fa]+1;
fa[t][0]=Fa;
fo(i,1,16) fa[t][i]=fa[fa[t][i-1]][i-1];
for (i=ls[t]; i; i=a[i][1])
if (a[i][0]!=Fa)
{
dfs(t,a[i][0]);
sz[t]+=sz[a[i][0]];
if (sz[a[i][0]]>mx)
mx=sz[a[i][0]],nx[t]=a[i][0];
}
}
void Dfs(int Fa,int t)
{
int i;
if (nx[t])
top[nx[t]]=top[t],Dfs(t,nx[t]);
for (i=ls[t]; i; i=a[i][1])
if (a[i][0]!=Fa && a[i][0]!=nx[t])
top[a[i][0]]=a[i][0],Dfs(t,a[i][0]);
}
void swap(int &x,int &y) {int z=x;x=y;y=z;}
int lca(int x,int y)
{
int i;
if (d[x]<d[y]) swap(x,y);
fd(i,16,0) if (d[fa[x][i]]>=d[y]) x=fa[x][i];
fd(i,16,0) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
if (x!=y) x=fa[x][0];
return x;
}
void add(int t,double X1,double X2,double Y1,double Y2)
{
if (abs(X1-X2)<=E)
{
b[t].push_back({X1,X1,0,Y1,1});
b[t].push_back({X1,X1,0,Y1,-1});
return;
}
double k=(Y2-Y1)/(X2-X1);
b[t].push_back({X1,X2,k,Y1-k*X1,1});
b[t].push_back({X2,X1,k,Y1-k*X1,-1});
}
void js(type a,type b)
{
double x,X1,X2;
if (abs(a.k-b.k)<=E)
{
if (abs(a.b-b.b)<=E)
{
X1=max(a.x1,b.x1),X2=min(a.x2,b.x2);
if (abs(X1-X2)<=E || X1<X2) ans=min(ans,X1);
}
return;
}
x=(a.b-b.b)/(b.k-a.k),X1=max(a.x1,b.x1),X2=min(a.x2,b.x2);
if ((abs(x-X1)<=E || X1<x) && (abs(x-X2)<=E || x<X2)) ans=min(ans,x);
}
void work(int t)
{
type s1,s2,C;
int i,j,k,l;
tot=0,l=b[t].size();
fo(i,0,l-1) c[++tot]=b[t][i];
sort(c+1,c+tot+1,cmp);
tt=c[1].x;
st.clear();
fo(i,1,tot)
if (abs(c[i].x-ans)>E && c[i].x<ans)
{
tt=c[i].x,I2=st.upper_bound({0,0,c[i].k,c[i].b});
if (c[i].s==1)
{
C={c[i].x,c[i].X,c[i].k,c[i].b};
if (I2!=st.end())
s2=*I2,js(C,s2);
if (I2!=st.begin())
--I2,s2=*I2,js(C,s2);
st.insert(C);
}
else
{
C={c[i].X,c[i].x,c[i].k,c[i].b};
if (I2!=st.begin() && I2!=st.end())
I1=I2,--I1,s1=*I1,s2=*I2,js(s1,s2);
st.erase(C);
}
}
else break;
}
int main()
{
#ifdef file
freopen("CF704E.in","r",stdin);
#endif
scanf("%d%d",&n,&m),ans=2147483647;
fo(i,1,n-1) scanf("%d%d",&j,&k),New(j,k),New(k,j);
dfs(0,1),top[1]=1,Dfs(0,1);
fo(i,1,m)
{
scanf("%lf%lf%d%d",&T,&C,&x,&y),Lca=lca(x,y),sum=d[x]+d[y]-d[Lca]*2,s1=s2=0;
while (1)
{
if (top[x]==top[y])
{
if (x==y) add(top[x],T+s1/C,T+s1/C,d[x],d[x]);
else
add(top[x],T+s1/C,T+(sum-s2)/C,d[x],d[y]);
break;
}
else
if (d[top[x]]>d[top[y]])
j=fa[top[x]][0],add(top[x],T+s1/C,T+(s1+(d[x]-d[j]))/C,d[x],d[j]),s1+=d[x]-d[j],x=j;
else
j=fa[top[y]][0],add(top[y],T+(sum-(s2+(d[y]-d[j])))/C,T+(sum-s2)/C,d[j],d[y]),s2+=d[y]-d[j],y=j;
}
}
fo(i,1,n)
if (!b[i].empty())
work(i);
if (ans>1000000000) printf("-1\n");
else printf("%.20lf\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}