题目描述

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

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

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

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

$$\max_{l \leq l' \leq r' \leq r \; \land \; r' - l' + 1 \geq k} \operatorname{dep}_{\operatorname{LCA}^*(l', r')} $$

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

输入格式

从文件 query.in 中读入数据。

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

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

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

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

输出格式

输出到文件 query.out 中。

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

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 解释

• 对于第一组询问，$\operatorname{LCA}^*(2, 3) = 2, \operatorname{LCA}^*(3, 4) = 2, \operatorname{LCA}^*(4, 5) = 6$，$2$ 的深度为 $3$，$6$ 的深度为 $2$，因此答案为 $\max\{3, 3, 2\} = 3$。
• 对于第二组询问，答案为 $1, 2, 3, 4$ 四个结点的最大深度，因此答案为 $4$。
• 对于第三组询问，$\operatorname{LCA}^*(1, 3) = 1, \operatorname{LCA}^*(2, 4) = 2, \operatorname{LCA}^*(3, 5) = 6, \operatorname{LCA}^*(4, 6) = 6$，依旧是 $2$ 的深度最大，因此答案为 $3$。

样例 2

见选手目录下的 query/query2.in 与 query/query2.ans。

该样例满足 $n, q \leq 500$。

样例 3

见选手目录下的 query/query3.in 与 query/query3.ans。

该样例满足 $n, q \leq 10^5$ 且树符合链的形态。

样例 4

见选手目录下的 query/query4.in 与 query/query4.ans。

该样例满足 $n, q \leq 5 \times 10^5$。

数据范围

对于所有的测试数据，保证：$1 \leq n, q \leq 5 \times 10^5$，$1 \leq l \leq r \leq n$，$1 \leq k \leq r − l + 1$。

测试点编号	$n, q \leq$	特殊限制
$1 \sim 2$	$500$	无
$3 \sim 5$	$5000$
$6 \sim 9$	$10^5$	满足性质 A
$10 \sim 13$	$5 \times 10^5$
$14 \sim 16$		满足性质 B
$17 \sim 20$	$10^5$	无
$21 \sim 25$	$5 \times 10^5$

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

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