logo AlgoBeat OnlineJudge
登录 注册

#214793. [RMI 2025] 电缆维护 / Engineers

内存限制:2048 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

由于官方未提供时限和空限,将 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> ,表示对所有 ,存在树边

返回符合条件的路径的最少数量。

输入格式

见「实现细节」。

输出格式

见「实现细节」。

样例

样例输入 1

5 3
1 10 3 8 6
0 1
1 2
2 3
2 4

样例输出 1

1

样例输入 2

20 30 
13 36 11 35 4 9 42 9 1 4 11 3 15 31 46 41 31 17 11 12
19 5
19 0
19 13
19 9
19 4
19 10
5 1
19 18
0 7
5 8
19 12
5 17
13 16
5 14
13 3
19 6
5 15
5 2
4 11

样例输出 2

3

数据范围与提示

样例解释

在样例一中,有 。树的结构如图所示:

::::align{center} ::::

一种合法的方案为构造路径

限制条件

  • 对所有 ,有
  • ,且 互不相同。

子任务

# 分值 约束
且对所有 ,有
且对所有 ,有
对所有 ,有
无额外约束。