Nearest Leaf
Contest: Codeforces Global Round 1
Difficulty rating: 2600
Tags: data structures, trees

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:

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.

Input format:
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 < 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$$$.

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

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
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$$$.

Example input:
5 3
1 10
1 1
3 2
3 3
1 1 5
5 4 5
4 1 2

Example output:
3
0
13

Example input:
5 3
1 1000000000
2 1000000000
1 1000000000
1 1000000000
3 4 5
2 1 5
2 4 5

Example output:
3000000000
1000000000
2000000000

Editorial:
Let's answer the queries offline: for each vertex we'll remember all queries for it.
Let's make vertex $$$1$$$ root and find distances from it to all leaves using DFS. Now for answering queries for vertex $$$1$$$ we should simply answer some range minimum queries, so we'll build a segment tree for it.
For answering queries for other vertices we will make segment trees with distances to leaves (like we did for handling queries for vertex $$$1$$$) for all vertices. We will traverse vertices of a tree using DFS and maintain actual distances to leaves in segment tree. Suppose, DFS went through edge $$$(u, v)$$$ with weight $$$w$$$ where $$$u$$$ is an ancestor of $$$v$$$. Distances to leaves in subtree of $$$v$$$ will decrease by $$$w$$$ and distances to other vertices will increase by $$$w$$$. Since set of leaves in subtree of some vertex is a subsegment of vertices written in euler traversal order, we should simply make range additions/subtractions on segment tree to maintain distances to leaves when passing through an edge.
This way we got a solution with $$$O(n \log n + q \log n)$$$ complexity.