Description
你在一颗树上旅行。
树由 $n$ 个点，$n - 1$ 条边构成，每条边的长度 $w$ 是 $1$ 或 $2$。
你要从点 $u$ 沿着唯一的简单路径走到点 $v$。但是，你的体力有限，所以一天之内最多只能走 $l$ 的距离。一天结束时待在树的节点外是很危险的，所以你必须在一天结束前到达某个节点并停下（可以刚好到达），即使你没有走到 $l$ 的距离。
给定这棵树和 $q$ 个询问，每个询问给出 $u,v,l$，请求出至少需要多少天。
数据范围 : $1 \leqslant n,q \leqslant 10^5, 1 \leqslant x,y,u,v \leqslant n,w \in \{1, 2\}, 2 \leqslant l \leqslant 2n.$
Tutorial
Lemma1: 一条路径，正着走和倒着走答案是一样的。
Proof1: 考虑将正着和倒着每天累计走的距离写下来，容易发现正着走相当于一开始落后了至多 $1$ 的距离，后面在不断追赶。可以发现在走的过程中是存在单调性的，所以正着走一定不可能超过倒着走，但也不可能落后超过 $1$。由于最后会走到相同的位置，所以答案是一样的。
有了上述引理，我们就可以考虑分别计算 $u$ 和 $v$ 分别跳到 $\textrm{LCA}(u, v)$ 下面最高能跳到的点的答案。设 $l_1, l_2$ 分别表示 $u$ 和 $v$ 剩下的距离，最终答案即为 $u$ 和 $v$ 的答案之和加上 $\left\lceil\frac{l_1 + l_2}{l}\right\rceil$。
考虑对询问根号分治，分别处理 $l \leqslant \sqrt{n}$ 的询问和 $l > \sqrt{n}$ 的询问。
- 对于 $l > \sqrt{n}$ 的询问，可以发现其跳的次数不超过 $\sqrt{n}$，于是可以直接暴力跳，用倍增维护一下即可。
- 对于 $l \leqslant \sqrt{n}$ 的询问，可以预处理出从每个点 $u$ 开始，此时的 $l = k$，往上跳 $2 ^ i$ 天到的点 $f_{u, k, i}$，倍增往上跳即可。
时间复杂度 $\Theta(n \sqrt{n} \log n)$，卡一卡常可以通过。
考虑换一种思路，我们给树上 $\sqrt{n}$ 个点打上标记，称它们为特殊点。那么如果标记打得足够均匀，就可以使 $u, v \to \textrm{LCA}(u, v)$ 的路径上每隔 $\sqrt{n}$ 的距离经过一个特殊点，且总共经过 $\sqrt{n}$ 个特殊点。至于如何打标记，可以记 $dis_u$ 表示 $u$ 到树上最远点的距离，取 $B = \sqrt{n}$，$u$ 为标记点当且仅当 $B | dis_u$。
考虑预处理 $f_{u, k}$ 表示当 $l = k$ 时，从 $u$ 开始走一天到的点（如果这个点超过了 $u$ 祖先中最深的特殊点，那么就将 $f_{u, k}$ 设为该特殊点，并且计算剩下了多少距离），$g_{u, k}$ 表示当 $l = k$ 时，从 $u$ 开始走到 $u$ 祖先中最深的特殊点需要花费的天数。
容易发现，由于走到 $u$ 祖先中最深的特殊点最多 $2\sqrt{n}$ 的距离，所以 $k$ 的取值范围为 $[0, 2\sqrt{n}]$。预处理直接从上往下递推即可，由于状态总数是 $n \sqrt{n}$ 的，所以预处理时间复杂度也是 $\Theta(n \sqrt{n})$。至于如何使用这两个数组优化往上跳的过程则是简单的，不作赘述。
总时间复杂度 $\Theta(n \sqrt{n})$，可以轻松通过此题。