#216476. [APIO 2026 中国赛区] 集宝

提交时请选择高于 C++17 的语法标准，不要引入头文件 gems.h。

第一千届收集宝石大赛开始了！

观众们都厌倦了发生在线性序列上的集宝问题，因此本次大赛相比历届有着明显的创新：参赛选手现在需要在一棵 个结点的无根树上收集宝石。

这棵树上一共有 颗宝石，其中第 () 颗宝石拥有相应的二元组参数 ，表示当一名选手当前到达结点 的简单路径所含边数不超过 时，他就可以选择立刻收集这颗宝石（当然，也可以选择不收集）。

相应地，本次大赛的选手也热情高涨，总共有 名选手报名参赛。对于每名选手，他将会被分配一个出发结点 与一个收集宝石的区间 ，他需要完成以下任务：从结点 出发，不断选择当前结点的一条邻边并移动过去，依次收集第 至第 颗宝石，即按照 的顺序收集所有 颗宝石。

因为每名选手在参赛过程中都遇到了或多或少的路线规划难题，为了给出合理的评分，主办方找到了你。请你对每一名选手，计算出该选手完成收集任务所需移动的最小总边数。

【实现细节】

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序包含头文件 gems.h，即在程序开头加入以下代码：

#include "gems.h"

选手需要在提交的程序源文件 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);

• 分别表示测试点编号、树的结点数与宝石的数量。 表示该测试点为样例。
• 对于 ， 表示树的一条边。
• 对于 ， 表示第 颗宝石的两个参数。
• 对于每个测试点，该函数会被交互库调用恰好一次，且在所有 query 函数调用之前。

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

• 分别表示一名选手的出发结点与收集宝石的区间。
• 该函数需要返回该选手从结点 出发，依次收集第 至第 颗宝石所需移动的最小总边数。
• 对于每个测试点，该函数会被交互库调用恰好 次。

【测试程序方式】

选手可以在本题目录下使用如下命令编译得到可执行程序：

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

对于编译得到的可执行程序：

• 可执行文件将从标准输入读入以下格式的数据：
  • 输入的第一行包含三个非负整数 。
  • 输入的第 () 行包含两个正整数 。
  • 输入的第 行包含 个正整数 。
  • 输入的第 行包含 个非负整数 。
  • 输入的第 行包含一个正整数 。
  • 输入的第 () 行包含三个正整数 。

可执行文件将输出以下格式的数据至标准输出：

• 输出共 行，每行一个非负整数，表示 query 函数的返回值。

样例输入 1

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

样例输出 1

2
2

【样例 1 解释】

对于第一名选手，该选手需要从结点 出发，收集第 颗宝石。一种可能的收集路径为 ，共经过 条边。

对于第二名选手，该选手需要从结点 出发，收集第 颗宝石。一种可能的收集路径为 ，共经过 条边。

【数据范围】

对于所有测试数据，均有：

• ；
• 对于所有 ，均有 ，且所有的边构成一棵树；
• 对于所有 ，均有 且 ；
• ；
• 。

::cute-table{tuack} | 测试点编号 | | | 特殊性质 | |:---:|:---:|:---:|:---:| | | | | 无 | | | | | ^ | | | ^ | | ^ | | | | | A | | | ^ | ^ | B | | | ^ | ^ | C | | | | | 无 | | | | | ^ |

• 特殊性质 A：树的形态是一条链，即不存在度数超过 的结点。
• 特殊性质 B：对于所有 ，均有 。
• 特殊性质 C：。