#P18932. [2026多校联测]传输

[2026多校联测]传输

传输

题目描述

某数据中心有 nn 台服务器,编号从 11 到 nn。服务器之间由 n−1n−1 条单向数据传输线路连接。11 号服务器是源服务器,从它出发可以沿一条或多条线路到达其他所有服务器。

一名黑客准备在某个服务器上投放一种会自我复制的恶意程序。程序会从该服务器出发,沿着单向数据传输线路不断感染其它服务器。被程序感染的服务器数量称为感染规模。

管理员提前得知了黑客的计划,他可以在 kk 台服务器上部署防火墙。部署防火墙的服务器不会被感染,也不会继续传播恶意程序。

管理员会先选择至多 kk 台服务器部署防火墙,以尽可能降低最坏情况下的感染规模。之后,黑客会选择一台服务器投放程序,并使感染规模尽可能大。你的任务是计算最终的感染规模,即最终会被恶意程序感染的服务器数量。

输入格式

输入的第一行包含两个正整数 nn 和 kk,表示服务器数量和管理员可以部署的防火墙数量。

接下来有一行包含 n−1n-1 个整数 a1,a2,…,an−1a_1,a_2,\dots,a_{n-1},其中 aia_i 表示存在一条单向数据传输线路从 aia_i 号服务器通往 i+1i+1 号服务器。

输出格式

输出一行一个整数表示答案。

样例 1 输入

5 2
1 2 1 1

样例 1 输出

1

样例 2 输入

7 1
1 1 2 2 3 3

样例 2 输出

3

样例 3 输入

7 2
1 2 2 4 1 6

样例 3 输出

2

样例 4

见选手目录下的 transmit4.in 与 transmit4.ans。

样例 5

见选手目录下的 transmit5.in 与 transmit5.ans。

样例 6

见选手目录下的 transmit6.in 与 transmit6.ans。

样例 7

见选手目录下的 transmit7.in 与 transmit7.ans。

数据范围

对于所有测试数据,保证:1≤k<n≤1051\le k < n\le 10^5。

测试点编号 n≤n\le 特殊性质
1,21,2 2020 无
3∼83\sim 8 10001000
9,109,10 10510^5 A
11∼1411\sim14 ^ B
15∼2015\sim 20 无
  • 特殊性质 A:对于所有 1≤i<n1 \le i < n,有 ai=ia_i = i。
  • 特殊性质 B:k=1k=1。