← 返回题目列表

Codeforces · 1110/F

F. 最近的叶子

中文机器翻译题面 查看原题

让我们将树(无环的连通无向图)的欧拉遍历定义如下:考虑深度优先搜索算法,该算法遍历树的顶点并按访问顺序枚举它们(仅计算每个顶点的第一次访问)。该函数从顶点编号 $$$1$$$ 开始,然后从与当前顶点有一条边相连且尚未访问的所有顶点开始按递增编号顺序递归运行。正式地,您可以使用以下伪代码来描述该函数:

给定一棵加权树,其顶点使用上述算法用从 $$$1$$$ 到 $$$n$$$ 的整数枚举。

叶子是树的一个顶点,仅与另一个顶点连接。在给你的树中,顶点 $$$1$$$ 不是叶子。树中两个顶点之间的距离是它们之间的简单路径上的边的权重之和。

您必须回答以下类型的 $$$q$$$ 查询:给定整数 $$$v$$$、$$$l$$$ 和 $$$r$$$,找到从顶点 $$$v$$$ 到索引从 $$$l$$$ 到 $$$r$$$ 的叶子之一的最短距离。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$3 \leq n \leq 500\,000, 1 \leq q \leq 500\,000$$$) - 分别是树中的顶点数和查询数。

以下 $$$n - 1$$$ 行中的第 $$$(i - 1)$$$ 行包含两个整数 $$$p_i$$$ 和 $$$w_i$$$ ($$$1 \leq p_i < i, 1 \leq w_i \leq 10^9$$$),表示顶点 $$$p_i$$$ 之间的边和 $$$i$$$ 的权重为 $$$w_i$$$。

保证给定的边形成一棵树,并且按照欧拉遍历顺序枚举顶点,并且索引为 $$$1$$$ 的顶点不是叶子。

接下来的 $$$q$$$ 行描述查询。其中每个包含三个整数 $$$v_i$$$、$$$l_i$$$、$$$r_i$$$ ($$$1 \leq v_i \leq n, 1 \leq l_i \leq r_i \leq n$$$),描述查询的参数。保证至少有一个叶子的索引为$$$x$$$,使得$$$l_i \leq x \leq r_i$$$。

输出

输出 $$$q$$$ 整数 - 按照输入中给出的顺序查询的答案。

示例

输入 #1

5 3
1 10
1 1
3 2
3 3
1 1 5
5 4 5
4 1 2

输出 #1

3
0
13

输入 #2

5 3
1 1000000000
2 1000000000
1 1000000000
1 1000000000
3 4 5
2 1 5
2 4 5

输出 #2

3000000000
1000000000
2000000000

输入 #3

11 8
1 7
2 1
1 20
1 2
5 6
6 2
6 3
5 1
9 10
9 11
5 1 11
1 1 4
9 4 8
6 1 4
9 7 11
9 10 11
8 1 11
11 4 5

输出 #3

8
8
9
16
9
10
0
34

注意

在第一个示例中,树如下所示:

在第一个查询中,顶点 $$$1$$$ 的最近叶子是顶点 $$$4$$$,距离 $$$3$$$。在第二个查询中,顶点 $$$5$$$ 的最近叶子是距离 $$$0$$$ 的顶点 $$$5$$$。在第三个查询中,顶点 $$$4$$$ 最近的叶子是顶点 $$$4$$$;但是,它不在查询的 $$$[1, 2]$$$ 区间内。区间 $$$[1, 2]$$$ 中的唯一叶子是顶点 $$$2$$$,距顶点 $$$4$$$ 的距离为 $$$13$$$。