D. 树上查询
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

有一天小 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$$$ 的连续子区间的最近公共祖先深度的最大值，即

$$$$$$\max_{l\le l'\le r'\le r \land r'-l'+1\ge k}\text{dep}_ {\text{LCA*}(l', r')}$$$$$$

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

Input

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

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

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

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

Output

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

Example
Input
6
5 6
6 1
6 2
2 3
2 4
3
2 5 2
1 4 1
1 6 3
Output
3
4
3
Note

【样例 1 解释】

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

见附件的 query/query2.in 与 query/query2.ans。

该样例满足 $$$n, q ≤ 500$$$。

【样例 3】

见附件的 query/query3.in 与 query/query3.ans。

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

【样例 4】

见附件的 query/query4.in 与 query/query4.ans。

该样例满足 $$$n, q ≤ 5 × 10^5$$$。

【数据范围】

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

测试点编号$$$n,q\le$$$特殊限制
$$$1\sim2$$$$$$500$$$无
$$$3\sim5$$$$$$5000$$$无
$$$6\sim9$$$$$$10^5$$$满足性质 A
$$$10\sim13$$$$$$5\times10^5$$$满足性质 A
$$$14\sim16$$$$$$5\times10^5$$$满足性质 B
$$$17\sim20$$$$$$10^5$$$无
$$$21\sim25$$$$$$5\times10^5$$$无

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

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