CF704E Iron Man

(Updated: )
oi
,

题目链接：CF704E

  • 给定一棵 $n$ 个点的树。
  • 有 $m$ 个人，第 $i$ 个人会在 $t_{i}$ 时刻出现在 $v_{i}$ ，并以每时刻 $c_{i}$ 条边的速度向 $u_{i}$ 移动，到达 $u_{i}$ 立刻消 失。出现的时段是左闭右闭的，因此如果 $v_{i}=u_{i}$ ，则在 $t_{i}$ 时刻 $i$ 仍会出现。
  • 求第一次有人相遇的时刻，或判断始终无人相遇。
  • $n, m \leq 10^{5}, t_{i}, c_{i} \leq 10^{4}$ 。

Tutorial

不妨先考虑在序列上如何做，如果直接枚举任两个人判断显然是 $O(m^2)$ 的。

发现可以将其抽象成若干线段，而其交点必然是相邻两条线段最小，丢入一个 multiset 维护一下相邻点的差的最小值即可。

发现上树其实很简单，分重链轻链考虑即可。

$O(n+m\log m\log n)$。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
	Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
	Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
	Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
	Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
	Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10;
struct F{LL x,y;};
I bool operator < (Cn F& a,Cn F& b){return a.x*b.y<b.x*a.y;}
I bool operator == (Cn F& a,Cn F& b){return a.x*b.y==b.x*a.y;}
I bool operator <= (Cn F& a,Cn F& b){return a<b||a==b;}
I bool operator > (Cn F& a,Cn F& b){return b<a;}
I bool operator >= (Cn F& a,Cn F& b){return b<=a;}
I bool operator != (Cn F& a,Cn F& b){return !(a==b);}
I LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
I F O(LL x,LL y){LL g=gcd(x,y);return {x/g,y/g};}
I F operator + (Cn F& a,Cn F& b){return O(a.x*b.y+b.x*a.y,a.y*b.y);}
I F operator - (Cn F& a,Cn F& b){return O(a.x*b.y-b.x*a.y,a.y*b.y);}
I F operator - (Cn F& a){return {-a.x,a.y};}
I F operator * (Cn F& a,Cn F& b){return O(a.x*b.x,a.y*b.y);}
I F operator / (Cn F& a,Cn F& b){return O(a.x*b.y,a.y*b.x);}
I void operator += (F& a,Cn F& b){a=a+b;}
I void operator -= (F& a,Cn F& b){a=a-b;}
I F min(Cn F& a,Cn F& b){return a<b?a:b;}
I F max(Cn F& a,Cn F& b){return b<a?a:b;}
Cn F inf={(LL)2e9,1};
int n,m,sz[N],mx[N],d[N],f[N],top[N],dfn[N],bk[N],cnt;
#define vi vector<int>
#define pb push_back
vi G[N];
F Ti,Ans=inf;
I void B1(CI x=1,CI fa=0){d[x]=d[f[x]=fa]+(sz[x]=1);for(auto i:G[x]) i^fa&&(B1(i,x),sz[x]+=sz[i],sz[i]>sz[mx[x]]&&(mx[x]=i));}
I void B2(CI x=1,CI tp=1){if(bk[dfn[x]=++cnt]=x,top[x]=tp,mx[x]) B2(mx[x],tp);for(auto i:G[x]) i^f[x]&&i^mx[x]&&(B2(i,i),0);}
struct line{F k,b,l,r;};
I bool operator < (Cn line& x,Cn line& y){
	if(x.k*Ti+x.b==y.k*Ti+y.b) return x.l!=y.l?x.l<y.l:x.r!=y.r?x.r<y.r:x.k<y.k;
	return x.k*Ti+x.b<y.k*Ti+y.b;
}
#define vl vector<line>
vl H[N],L[N];
I int lca(RI x,RI y){
	W(top[x]^top[y])
		d[top[x]]>d[top[y]]?x=f[top[x]]:y=f[top[y]];
	return d[x]<d[y]?x:y;
}
I int Di(CI x,CI y){return d[x]+d[y]-2*d[lca(x,y)];}
I void Sp(RI u,RI v,F t,F c){
	F T=t+(F){Di(u,v),1}/c;W(top[u]^top[v]){
		if(d[top[u]]>d[top[v]]){
			RI p=top[u];
			H[p].pb({-c,(F){d[u],1}+c*t,t,t+(F){d[u]-d[p],1}/c});t+=(F){d[u]-d[p],1}/c,u=top[u],p=f[u];
			L[u].pb({-c,(F){d[u],1}+c*t,t,t+(F){d[u]-d[p],1}/c});t+=(F){d[u]-d[p],1}/c,u=f[u];
		}else{
			RI p=top[v];
			H[p].pb({c,(F){d[v],1}-c*T,T-(F){d[v]-d[p],1}/c,T});T-=(F){d[v]-d[p],1}/c,v=top[v],p=f[v];
			L[v].pb({c,(F){d[v],1}-c*T,T-(F){d[v]-d[p],1}/c,T});T-=(F){d[v]-d[p],1}/c,v=f[v];
		}
	}RI p=top[u];if(d[u]>d[v]) assert(T==t+((F){d[u]-d[v],1}/c)),H[p].pb({-c,(F){d[u],1}+c*t,t,T});else assert(t==T-((F){d[v]-d[u],1}/c)),H[p].pb({c,(F){d[v],1}-c*T,t,T});
}
I F Pt(line x,line y){
	if(x.k==y.k) return x.b==y.b&&max(x.l,y.l)<=min(x.r,y.r)?max(x.l,y.l):inf;
	F tk=(y.b-x.b)/(x.k-y.k);
	return tk>=max(x.l,y.l)&&tk<=min(x.r,y.r)?tk:inf;
}
I void Wk(vl v){
	F X=inf;
	#define mp make_pair
	#define pa pair<line,bool>
	#define fi first
	#define se second
	vector<pa> g;multiset<line> stk;for(auto i:v) g.pb(mp(i,1)),g.pb(mp(i,0));
	sort(g.begin(),g.end(),[&](Cn pa& x,Cn pa& y){F tx=x.se?x.fi.l:x.fi.r,ty=y.se?y.fi.l:y.fi.r;return tx==ty?x.se>y.se:tx<ty;});
	for(auto x:g){
		F o=x.se?x.fi.l:x.fi.r;
		if(o>=X) break ;
		if(Ti=o,x.se){
			stk.insert(x.fi);auto it=stk.lower_bound(x.fi),ip=it,is=it;++is;
			ip!=stk.begin()&&(--ip,X=min(X,Pt(*ip,*it)),0),is!=stk.end()&&(X=min(X,Pt(*it,*is)),0);
		}else{
			auto it=stk.lower_bound(x.fi),ip=it,is=it;++is;
			ip!=stk.begin()&&is!=stk.end()&&(--ip,X=min(X,Pt(*ip,*is)),0),stk.erase(it);
		}
	}Ans=min(Ans,X);
}
int main(){
//	freopen("1.in","r",stdin);
	RI i,x,y,t,c,u,v;for(read(n,m),i=1;i<n;i++) read(x,y),G[x].pb(y),G[y].pb(x);
	for(B1(),B2(),i=1;i<=m;i++) read(t,c,u,v),Sp(u,v,{t,1},{c,1});
	for(i=1;i<=n;i++) Wk(H[i]),Wk(L[i]);
	long double O=1.0*Ans.x/Ans.y;return printf("%.7Lf",O>=2e9?-1:O),0;
}