P16435 [APIO 2026 China Region] Gem Collecting

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

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: ```cpp #include "gems.h" ``` You need to implement the following two functions in the submission source file `gems.cpp`: ```cpp void gems(int c, int n, int m, std::vector u, std::vector v, std::vector a, std::vector 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. ```cpp 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: ```bash g++ grader.cpp gems.cpp -o gems -O2 -std=c++14 -static ```

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

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.

### 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