#NOIP2024D. 树上查询(query)民间数据

树上查询(query)民间数据

[NOIP2024] 树上查询(民间数据)

题目背景

2s 1024MB

题目描述

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

这是一棵有根树,根结点编号为 11,每个结点 uu 的深度 depu\text{dep}_ u 定义为 uu11 的简单路径上的结点数量

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

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

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

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

输入格式

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

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

n+1n + 1 行包含一个正整数 qq,表示询问的数量。

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

3
4
3

提示

【样例 1 解释】

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

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

  • 对于第三组询问,$\text{LCA*}(1, 3) = 1, \text{LCA*}(2, 4) = 2, \text{LCA*}(3, 5) = 6, \text{LCA*}(4, 6) = 6$,依旧是 22 的深度最大,因此答案为 33

【样例 2】

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

该样例满足 n,q500n, q ≤ 500

【样例 3】

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

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

【样例 4】

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

该样例满足 n,q5×105n, q ≤ 5 × 10^5

【数据范围】

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

测试点编号 n,qn,q\le 特殊限制
121\sim2 500500
353\sim5 50005000
696\sim9 10510^5 满足性质 A
101310\sim13 5×1055\times10^5
141614\sim16 满足性质 B
172017\sim20 10510^5
212521\sim25 5×1055\times10^5

性质 A:保证输入的树符合链的形态,且根结点的度数为 11

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