7265 - 树上查询（query）

有一天小 S 和她的朋友小 N 一起研究一棵包含了 n 个结点的树。

这是一棵有根树，根结点编号为 1，每个结点 u 的深度 \text{dep}_ u 定义为 u 到 1 的简单路径上的结点数量。

除此之外，再定义 \text{LCA*}(l, r) 为编号在 [l, r] 中所有结点的最近公共祖先，即 l, l + 1, \dots , r 的公共祖先结点中深度最大的结点。

小 N 对这棵树提出了 q 个询问。在每个询问中，小 N 都会给出三个参数 l, r, k，表示他想知道 [l, r] 中任意长度大于等于 k 的连续子区间的最近公共祖先深度的最大值，即

你的任务是帮助小 S 来回答这些询问。

输入的第一行包含一个正整数 n，表示树的结点数。

接下来 n - 1 行，每行包含两个正整数 u, v，表示存在一条从结点 u 到结点 v 的边。

第 n + 1 行包含一个正整数 q，表示询问的数量。

接下来 q 行，每行包含三个正整数 l, r, k，描述了一次询问。

对于每次询问输出一行，包含一个整数，表示对应的答案。

【样例 1 解释】

• 对于第一组询问，$LCA (2, 3) = 2 , LCA (3, 4) = 2, LCA * (4, 5) = 6，2 的深度为 3，6 的深度为 2，因此答案为 max{3, 3, 2} = 3$。

• 对于第二组询问，答案为 1, 2, 3, 4 四个结点的最大深度，因此答案为 4。

• 对于第三组询问，$LCA(1, 3) = 1, LCA (2, 4) = 2, LCA (3, 5) = 6,LCA (4, 6) = 6，依旧是 2 的深度最大，因此答案为 3$。

【数据范围】

对于所有的测试数据，保证：1 ≤ n, q ≤ 5 × 10^5, 1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ r - l + 1

性质 A：保证输入的树符合链的形态，且根结点的度数为 1。

性质 B：对于每个询问保证 k = r - l + 1。

NOIP