A5655 | $「NOIP2024」树上查询$

时间限制2s

内存限制512MB

通过 / 提交0/0

题目描述

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

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

输出到文件 query.out 中。 对于每次询问输出一行，包含一个整数，表示对应的答案。

输入 #1

输出 #1

3
4
3

C++ 编辑器

输入

输出