P6890 [CEOI 2006] Link

题目描述

给出 $N$ 个点的内向基环树森林，求最少加多少条边使得 $1$ 到每个点的最短路均不超过 $k$。

输入格式

第一行是两个整数用空格隔开 $N$ 和 $K$。

接下来 $N$ 行：

其中第 $i+1$ 行 $(1\leqslant i\leqslant N)$ 输入两个整数 $x$ 和 $y$，表示存在一条从 $x$ 到 $y$ 的单向边。

输出格式

输出仅一个整数：表示最少需要添加的边数。

输入输出样例 #1

输入 #1

8 3
1 2
2 3
3 5
4 5
5 6
6 7
7 8
8 5

输出 #1

2

输入输出样例 #2

输入 #2

14 4
1 2
2 3
3 4
4 5
7 5
5 6
6 3
8 10
10 9
9 8
14 13
13 12
12 11
11 14

输出 #2

3

说明/提示

在第二组样例中，一个合法的路径集合 $\{1\to 7,1\to 14,14\to 10\}$。

$2 \leq N \leq 500 000$, $1 \leq K \leq 20 000$。

题面翻译由 ChatGPT-4o 提供。