一道不确定是否为证明题的题目,求证明或证伪
  • 板块学术版
  • 楼主pxb0801
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/9/24 20:44
  • 上次更新2023/11/2 18:15:00
查看原帖
一道不确定是否为证明题的题目,求证明或证伪
372838
pxb0801楼主2023/9/24 20:44

题面:

给定一个顶点数为 nn (编号为 1∼n1 \sim n),边数为 n−1n-1 的连通图。图中有 mm 个顶点是特殊的点,已被染色为红色,其它所有的点均为白色,现在要你求最多可以删除多少条边,使得图中白色顶点到离它最近的红色顶点的距离小于等于 dd(初始时每一个白点到最近红点的距离均小于等于 dd)。

输入格式:

第一行三个整数 n,m,dn,m,d。

第二行 mm 整数 p1,⋯ ,pmp_1, \cdots,p_m,表示 mm 个红色顶点的编号(可能有编号相同的点)。

接下来 n−1n-1 行,每行两个整数 u,vu,v,表示顶点 uu 与 vv 之间有一条边。

输出格式:

输出一行包含一个整数,表示能删除的最多边数。

感觉输出是将红色顶点的节点去重后的数量 −1-1。求证明或证伪

2023/9/24 20:44
加载中...