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 \gt \sqrt{n}\) 的询问。
- 对于 \(l \gt \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})\)，可以轻松通过此题。
