CF1110F.Nearest Leaf

Let's define the Eulerian traversal of a tree (a connected undirected graph without cycles) as follows: consider a depth-first search algorithm which traverses vertices of the tree and enumerates them in the order of visiting (only the first visit of each vertex counts). This function starts from the vertex number $1$ and then recursively runs from all vertices which are connected with an edge with the current vertex and are not yet visited in increasing numbers order. Formally, you can describe this function using the following pseudocode:

next_id = 1
id = array of length n filled with -1
visited = array of length n filled with false

function dfs(v):
visited[v] = true
id[v] = next_id
next_id += 1
for to in neighbors of v in increasing order:
if not visited[to]:
dfs(to)

You are given a weighted tree, the vertices of which were enumerated with integers from $1$ to $n$ using the algorithm described above.

A leaf is a vertex of the tree which is connected with only one other vertex. In the tree given to you, the vertex $1$ is not a leaf. The distance between two vertices in the tree is the sum of weights of the edges on the simple path between them.

You have to answer $q$ queries of the following type: given integers $v$, $l$ and $r$, find the shortest distance from vertex $v$ to one of the leaves with indices from $l$ to $r$ inclusive.

我们定义一棵树（即无环的连通无向图）的欧拉遍历如下：考虑一种深度优先搜索（DFS）算法，该算法遍历树的顶点，并按首次访问的顺序对顶点进行编号（每个顶点仅计入其第一次被访问时的时刻）。该函数从编号为 $1$ 的顶点开始，然后按顶点编号递增的顺序，依次对当前顶点所有未访问过的邻接顶点递归执行该过程。形式化地，该函数可用如下伪代码描述：

next_id = 1
id = 长度为 $n$ 的数组，初始值全为 $-1$
visited = 长度为 $n$ 的数组，初始值全为 false

function dfs(v):
visited[v] = true
id[v] = next_id
next_id += 1
for to in v 的邻接顶点（按编号升序排列）:
if not visited[to]:
dfs(to)

你将得到一棵带权树，其顶点编号 $1$ 到 $n$ 正是通过上述算法得到的。

叶子节点是指在树中仅与一个其他顶点相连的顶点。在本题所给的树中，顶点 $1$ 不是叶子节点。树中两个顶点之间的距离定义为它们之间唯一简单路径上所有边的权重之和。

你需要回答 $q$ 个如下类型的查询：给定整数 $v$、$l$ 和 $r$，求顶点 $v$ 到下标在区间 $[l, r]$ 内（含端点）的所有叶子节点的最短距离。

The first line contains two integers $n$ and $q$ ($3 \leq n \leq 500\,000, 1 \leq q \leq 500\,000$) — the number of vertices in the tree and the number of queries, respectively.

The $(i - 1)$-th of the following $n - 1$ lines contains two integers $p_i$ and $w_i$ ($1 \leq p_i \lt i, 1 \leq w_i \leq 10^9$), denoting an edge between vertices $p_i$ and $i$ with the weight $w_i$.

It's guaranteed that the given edges form a tree and the vertices are enumerated in the Eulerian traversal order and that the vertex with index $1$ is not a leaf.

The next $q$ lines describe the queries. Each of them contains three integers $v_i$, $l_i$, $r_i$ ($1 \leq v_i \leq n, 1 \leq l_i \leq r_i \leq n$), describing the parameters of the query. It is guaranteed that there is at least one leaf with index $x$ such that $l_i \leq x \leq r_i$.

第一行包含两个整数 $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 \lt 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$），表示该查询的参数。保证在下标范围 $[l_i, r_i]$ 内至少存在一个叶子节点。

Output $q$ integers — the answers for the queries in the order they are given in the input.

输出 $q$ 个整数——按输入中查询的顺序给出各查询的答案。

In the first example, the tree looks like this:

In the first query, the nearest leaf for the vertex $1$ is vertex $4$ with distance $3$. In the second query, the nearest leaf for vertex $5$ is vertex $5$ with distance $0$. In the third query the nearest leaf for vertex $4$ is vertex $4$; however, it is not inside interval $[1, 2]$ of the query. The only leaf in interval $[1, 2]$ is vertex $2$ with distance $13$ from vertex $4$.

在第一个例子中，树的结构如下：

在第一个查询中，顶点 $1$ 的最近叶节点是顶点 $4$，距离为 $3$。在第二个查询中，顶点 $5$ 的最近叶节点是其自身（即顶点 $5$），距离为 $0$。在第三个查询中，顶点 $4$ 的最近叶节点仍是顶点 $4$；然而，该顶点不在查询所指定的区间 $[1, 2]$ 内。区间 $[1, 2]$ 中唯一的叶节点是顶点 $2$，它到顶点 $4$ 的距离为 $13$。