我们先定义 回头路：表示 $u[i]$ 前往 $u[i+1]$ 的路径经过了 $u[i-1]$ 前往 $u[i]$ 的路径，不回头路 反之。

如果前往下一个点 $u[i]$ 的路径是回头路，那么我们可以走的最远距离是上一个点剩余的移动步数 $rd[i-1]$ 加上撤销路径长度 $rb$ 加上当前移动步数：$len=rd[i-1] + rb + v*( t[i]-t[i-1])$。

如果前往下一个点 $u[i]$ 的路径是不回头路，那么我们可以走的最远距离是上一个点剩余的移动步数加上当前移动步数：$len=rd[i-1] + v*( t[i]-t[i-1])$。

若最远距离无法抵达下一个点，那么我们可以贪婪地增加 $v$ 值。

那么问题来了，如何求撤销路径长度 $rb$ 呢？

我们可以发现 $x$ 到 $y$ 的树上 弯路径 可以拆分成 直路径 $(x,lca(x,y))$ 和 $(lca(x,y),y)$，那么回头路存在的必要条件就是 $z$ 点与 $x$ 或 $y$ 的 LCA 交于这两条直路径，那么我们贪婪地选择 $(y,lca(z,y))$ 和 $(y,lca(z,x))$ 中最长的就是撤销路径长度。

LCA 和两点路径长度可以通过 倍增算法 在线查询。

复杂度：时间 $O(nlogn)$，空间 $O(nlogn)$。

先考虑链上如何完成。容易发现，任意 $T_i$ 天，旅行者可能在的位置在链上是一个区间 $[L_i,R_i]$。

二分答案，速度为 $v$，则每天可能所在的区间由 $[L,R]$ 变为 $[L-v,R+v]$。每当遇见一个限制，则取区间交作为新的可能区间。复杂度 $O(nlogn)$。

树上做法是一样的。定义 $D(u,d)$ 表示距离 $u$ 小于等于 $d$ 的点集，可以给出一个构造性证明，任意两组 $D$ 相交仍然能用 $D(...,...)$ 表示。

那么做法是一样的，需要支持的操作为求 lca 和从一个点往另一个点走 $k$ 步。二者均可做到 $O(nlogn)-O(1)$。

故总复杂度 $O(nlogn)$。

Cir mer(Cir a,Cir b) { // 构造性证明, Cir(u,r)=D(u,r)
	int d=dist(a.v,b.v); 
	if(a.r>=b.r+d) return b; 
	if(b.r>=a.r+d) return a; 
	if(a.r+b.r<d) return Cir(-1,-1);
	return Cir(go(a.v,b.v,a.r-(a.r+b.r-d)/2),(a.r+b.r-d)/2); 
}