Background

When submitting, please choose a language standard higher than C++17, and do not include the header file gems.h.

Problem Description

The 1000th Gem Collecting Contest has begun.

The audience is tired of gem collecting problems on linear sequences, so this contest has a clear innovation compared to previous ones: contestants now need to collect gems on an unrooted tree with $n$ nodes.

There are $m$ gems on the tree. The $i$-th gem ($1 \le i \le m$) has a pair of parameters $(a_i, d_i)$, meaning that when a contestant is currently at a node whose simple path to node $a_i$ contains at most $d_i$ edges, they may choose to collect this gem immediately (of course, they may also choose not to collect it).

At the same time, many contestants have signed up, with a total of $q$ contestants. For each contestant, they are assigned a starting node $x$ and a gem interval $[l, r]$. They need to complete the following task: starting from node $x$, repeatedly choose an adjacent edge of the current node and move across it, and collect gems from the $l$-th to the $r$-th in order, i.e., collect all $r - l + 1$ gems in the order $l, l + 1, \dots, r$.

Since each contestant encounters more or less route planning difficulties during the contest, the organizer has found you to provide a reasonable scoring method. For each contestant, compute the minimum total number of edges they need to traverse to complete the collection task.

Implementation Details

You do not need to, and should not, implement the main function.

You must ensure that the submitted program includes the header file gems.h, i.e., add the following code at the beginning of the program:

#include "gems.h"

You need to implement the following two functions in the submission source file gems.cpp:

void gems(int c, int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> d);

• $c, n, m$ represent the test point ID, the number of nodes in the tree, and the number of gems, respectively. $c = 0$ means this test point is the sample.
• For $0 \le i < n - 1$, $u_i, v_i$ represent an edge of the tree.
• For $0 \le i < m$, $a_i, d_i$ represent the two parameters of the $(i + 1)$-th gem.
• For each test point, this function will be called by the interaction library exactly once, and before any query function calls.

long long query(int x, int l, int r);

• $x, l, r$ represent a contestant’s starting node and gem interval.
• This function should return the minimum total number of edges the contestant needs to traverse when starting from node $x$ and collecting gems from the $l$-th to the $r$-th in order.
• For each test point, this function will be called by the interaction library exactly $q$ times.

Testing Program Method

You can compile an executable in this problem directory using the following command:

g++ grader.cpp gems.cpp -o gems -O2 -std=c++14 -static

Input Format

For the compiled executable:

• The executable will read data from standard input in the following format:
  • The first line contains three non-negative integers $c, n, m$.
  • Line $(1 + i)$ ($1 \le i \le n - 1$) contains two positive integers $u_i, v_i$.
  • Line $(n + 1)$ contains $m$ positive integers $a_1, a_2, \dots, a_m$.
  • Line $(n + 2)$ contains $m$ non-negative integers $d_1, d_2, \dots, d_m$.
  • Line $(n + 3)$ contains one positive integer $q$.
  • Line $(n + 3 + i)$ ($1 \le i \le q$) contains three positive integers $x, l, r$.

Output Format

The executable will output data to standard output in the following format:

• Output a total of $q$ lines, each containing one non-negative integer, which is the return value of the query function.

0 5 4
1 2
1 3
2 4
2 5
4 1 5 3
1 0 1 2
2
2 2 4
4 1 2

2
2

Hint

Sample 1 Explanation

For the first contestant, they need to start from node $2$ and collect gems $2 \sim 4$. One possible collection path is $2 \to 1 \to 2 \to 2$, passing through $2$ edges in total.

For the second contestant, they need to start from node $4$ and collect gems $1 \sim 2$. One possible collection path is $4 \to 2 \to 1$, passing through $2$ edges in total.

Constraints

For all testdata, we have:

• $2 \le n \le 3 \times 10^5, 1 \le m \le 3 \times 10^5$.
• For all $1 \le i \le n - 1$, $1 \le u_i, v_i \le n$, and all edges form a tree.
• For all $1 \le i \le m$, $1 \le a_i \le n$ and $0 \le d_i \le n$.
• $1 \le q \le 5 \times 10^5$.
• $1 \le x \le n, 1 \le l \le r \le m$.

::cute-table{tuack} | Test Point ID | $n, m \le$ | $q \le$ | Special Property | |:---:|:---:|:---:|:---:| | $1 \sim 3$ | $10^2$ | $10^2$ | None | | $4 \sim 7$ | $10^3$ | $10^3$ | ^ | | $8 \sim 10$ | ^ | $3 \times 10^5$ | ^ | | $11, 12$ | $3 \times 10^5$ | $5 \times 10^5$ | A | | $13, 14$ | ^ | ^ | B | | $15 \sim 17$ | ^ | ^ | C | | $18 \sim 21$ | $10^5$ | $3 \times 10^5$ | None | | $22 \sim 25$ | $3 \times 10^5$ | $5 \times 10^5$ | ^ |

• Special Property A: The tree is a chain, i.e., there is no node with degree greater than $2$.
• Special Property B: For all $1 \le i \le m$, $d_i \ge n/2$.
• Special Property C: $l = 1$.

Translated by ChatGPT 5