[CF704E] Iron man

题目链接

树的情况不好做。先树剖，现在变成了链的问题。

考虑对时间扫描线，会发现所有人的相对顺序变化的时候，就是有人相遇了。所以他的相对顺序可以用一个 set 维护。而将会相遇的人一定是插入时相对顺序相邻的人，可以 check 一下取个最小值。可以把时间线设成全局变量，这样就可以跑 set 的排序了。

// LUOGU_RID: 136377501
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const double eps=1e-10;
int n,m,u,v,fa[N],sz[N],son[N],dep[N],tp[N];
double tme,ans=1e9;
vector<int>g[N];
struct node{
	int l;
	double op,s,t;
	double ask(double t)
	{
		return l+op*(t-s);
	}
	bool operator<(const node&n)const{
		return l+op*(tme-s)<n.l+n.op*(tme-n.s);
	}
};
struct caozuo{
	double t;
	int op;
	node x;
	bool operator<(const caozuo&c)const{
		if(fabs(t-c.t)>=eps)
			return t<c.t;
		return op>c.op;
	}
}st[N<<1];
vector<node>h[N];
set<node>s;
void dfs(int x,int y)
{
	dep[x]=dep[y]+1;
	fa[x]=y;	
	sz[x]=1;
	for(int v:g[x])
	{
		if(v^y)
		{
			dfs(v,x),sz[x]+=sz[v];
			if(sz[v]>sz[son[x]])
				son[x]=v;
		}
	}
}
void sou(int x,int y,int p)
{
	tp[x]=p;
	if(son[x])
		sou(son[x],x,p);
	for(int v:g[x])
		if(v^y&&v^son[x])
			sou(v,x,v);
}
int dis(int u,int v)
{
	int ans=0;
	while(tp[u]^tp[v])
	{
		if(dep[tp[u]]<dep[tp[v]])
			swap(u,v);
		ans+=dep[u]-dep[fa[tp[u]]];
		u=fa[tp[u]];
	}
	ans+=abs(dep[u]-dep[v]);
	return ans;
}
void add(int u,int v,int t,double c)
{
	double cu=t,cv=t+dis(u,v)/c;
	while(tp[u]^tp[v])
	{
		if(dep[tp[u]]>dep[tp[v]])
		{
			h[tp[u]].push_back((node){dep[u]-dep[fa[tp[u]]],-c,cu,cu+(dep[u]-dep[tp[u]]+1)/c});
			cu+=(dep[u]-dep[tp[u]]+1)/c;
			u=fa[tp[u]];
		}
		else
		{
			h[tp[v]].push_back((node){0,c,cv-(dep[v]-dep[tp[v]]+1)/c,cv});
			cv-=(dep[v]-dep[tp[v]]+1)/c;
			v=fa[tp[v]];
		}
	}
	if(dep[u]<dep[v])
		h[tp[u]].push_back((node){dep[u]-dep[tp[u]]+1,c,cu,cv});
	else
		h[tp[v]].push_back((node){dep[u]-dep[tp[u]]+1,-c,cu,cv});
}
void chk(node x,node y)
{
	double t=min(x.t,y.t);
	if(x.ask(t)-y.ask(t)>=-eps)
	{
		if(x.op==y.op)
			ans=min(ans,max(x.s,y.s));
		else
			ans=min(ans,(x.l-y.l+y.op*y.s-x.op*x.s)/(y.op-x.op));
	}
}
mt19937 gen(time(0));
int main()
{
//	n=1000,m=1024;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
//		u=i+1,v=gen()%i+1;
		g[u].push_back(v),g[v].push_back(u);
	}
	dfs(1,0);
	sou(1,0,1);
	while(m--)
	{
		int u,v,t,c;
//		t=gen()%1000,c=gen()%100,u=gen()%n+1,v=gen()%n+1;
		scanf("%d%d%d%d",&t,&c,&u,&v);
		add(u,v,t,c);
	}
	for(int i=1;i<=n;i++)
	{
		if(tp[i]^i)
			continue;
		int m=0;
		for(node j:h[i])
			st[++m]=(caozuo){j.s,1,j},st[++m]=(caozuo){j.t,-1,j};
		sort(st+1,st+m+1);
		s.clear();
		for(int j=1;j<=m;j++)
		{
			if(st[j].t-ans>-eps)
				break;
			tme=st[j].t;
			set<node>::iterator itl,itr;
			if(st[j].op==-1)
			{
				s.erase(s.lower_bound(st[j].x));
				itr=s.lower_bound(st[j].x);
				if(itr!=s.begin()&&itr!=s.end())
				{
					itl=--itr;
					++itr; 
					chk(*itl,*itr);
				}
			}
			else
			{
				itr=s.lower_bound(st[j].x);
				if(itr!=s.end())
					chk(st[j].x,*itr);
				if(itr!=s.begin())
					chk(*(--itr),st[j].x);
				s.insert(st[j].x);
			}
		}
	}
	if(ans==1e9)
		puts("-1");
	else
		printf("%.10lf",ans);
}