题目描述
有一天小 S 和她的朋友小 N 一起研究一棵包含了 n 个结点的树。
这是一棵有根树,根结点编号为 1,每个结点 u 的深度 depu 定义为 u 到 1 的简单路径上的结点数量。
除此之外,再定义 LCA*(l,r) 为编号在 [l,r] 中所有结点的最近公共祖先,即 l,l+1,…,r 的公共祖先结点中深度最大的结点。
小 N 对这棵树提出了 q 个询问。在每个询问中,小 N 都会给出三个参数 l,r,k,表示他想知道 [l,r] 中任意长度大于等于 k 的连续子区间的最近公共祖先深度的最大值,即
l≤l′≤r′≤r∧r′−l′+1≥kmaxdepLCA*(l′,r′)你的任务是帮助小 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。
【样例 2】
见附件的 query/query2.in 与 query/query2.ans。
该样例满足 n,q≤500。
【样例 3】
见附件的 query/query3.in 与 query/query3.ans。
该样例满足 n,q≤105 且树符合链的形态。
【样例 4】
见附件的 query/query4.in 与 query/query4.ans。
该样例满足 n,q≤5×105。
【数据范围】
对于所有的测试数据,保证:1≤n,q≤5×105,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。