由于官方未提供时限和空限,将 TL 设置为 std 的两倍,ML 设置为 2G。
给定一棵 个点的树,点编号 。点 有正整数点权 。
给定正整数 。构造若干条简单路径(点集可以有交),使得未被路径覆盖的点的点权差值不大于 。
形式化地说,设未被覆盖的点集为 ,你需要保证 ,都有 。
在满足上述条件的前提下最小化路径数量。只需要求出路径数量。
实现细节
这是一道(函数式)交互题。你不需要,也不应该定义 main 函数。
你需要实现函数
int solve(int N, int D, std::vector<int> C, std::vector<int> P, std::vector<int> Q)
该函数接收以下参数:
- 点数 ;
- 最大可接受差值 ;
- 点权 ;
- 两个长度为 的
vector<int> 和 ,表示对所有 ,存在树边 。
返回符合条件的路径的最少数量。