题目描述

有一天小 S 和她的朋友小 N 一起研究一棵包含了 $n$ 个结点的树。 这是一棵有根树，根结点编号为 $1$，每个结点 $u$ 的深度 $dep_u$ 定义为 $u$ 到 $1$ 的简单路径上的结点数量。 除此之外，再定义 $LCA∗(l, r)$ 为编号在 [$l$, $r$] 中所有结点的最近公共祖先，即 $l$, $l +1$, · · · , $r$ 的公共祖先结点中深度最大的结点。 小 N 对这棵树提出了 $q$ 个询问。在每个询问中，小 N 都会给出三个参数 $l$, $r$, $k$，表示他想知道 [$l$, $r$] 中任意长度大于等于 $k$ 的连续子区间的最近公共祖先深度的最大值，即 $\begin {matrix}max\\l≤ l'≤r'≤r \land\ r'-l'+1≥k \end{matrix}dep_{LCA*(l',r')}$ 你的任务是帮助小 S 来回答这些询问。

输入

输入的第一行包含一个正整数 $n$，表示树的结点数。 接下来 $n − 1$ 行，每行包含两个正整数 $u$, $v$，表示存在一条从结点 $u$ 到结点 $v$ 的边。 第 $n + 1$ 行包含一个正整数 $q$，表示询问的数量。 接下来 $q$ 行，每行包含三个正整数 $l$, $r$, $k$，描述了一次询问。

输出

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

输入样例

6
5 6
6 1
6 2
2 3
2 4
3
2 5 2
1 4 1
1 6 3

输出样例

3
4
3

提示

【样例 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$

测试点编号	n, q ≤	特殊限制
1 ∼ 2	500	无
3 ∼ 5	5000
6 ∼ 9	105	满足性质 A
10 ∼ 13	5 × 105
14 ∼ 16		满足性质 B
17 ∼ 20	105	无
21 ∼ 25	5 × 105

性质 A：保证输入的树符合链的形态，且根结点的度数为 $1$。 性质 B：对于每个询问保证 $k = r − l + 1$。

本地评测资源说明

原题内存上限为1024MiB。本机采用更严格的512MiB单题上限，原始资源限制另存来源复核记录；参考程序已在此上限完成全部评测点核验。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共7个测试点，非原站或官方原始数据。总分100分。