#1887. 捉迷藏

捉迷藏

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

位于1\red{1}城市长达三小时的小云雀杯结束了,困扰了小Z很久的问题也得以解决。大家都争先恐后的要前往小Z家里。去看看小Z家的花目前是什么样子。当他们兴致勃勃的到达小Z家里时,发现花都不见了,大家愣了一会,终于反映过来了。高喊:快报警,抓小偷了。 但是附近有这么多城市,谁知道小偷跑哪去了呢。但是因为小偷从花园走出去的,所以它身上有香味,我们每一次都可以知道他在哪一个城市。

总共有n\red{n(}n<=200000\red{n <= 200000)}个城市,小偷已经跑到了第m(m<=n)\red{m( m <= n)}个城市。 有趣的是,所有的城市是一个树形结构。对于学过信息学的你来说,这个根本不算特别难的问题。

规则:警察追击小偷为回合制。但是小偷会先转移。小偷转移时也可原地不动,但是要算一次转移次数。小偷移动完成以后警察才可以移动。

小偷尽可能的拖延时间,警察要快点抓住小偷

请帮助警察,用最快的时间抓住小偷

输入格式

第一行输入n\red{n}m\red{m}

接下来总共n1\red{n-1}行,每行输入2\red{2}个数a,b\red{a,b,}表示a\red{a}城市和b\red{b}城市之间有道路,可以到达。

输出格式

共一行,输出警察抓到小偷的时候的最短时间。

样例

输入样例1

4 3
1 2
2 3 
2 4

输出样例1

4

输入样例2

5 2 
1 2
2 3 
3 4
2 5

输出样例2

6

提示

样例1\red{1}解释:

图一:

img

小偷在3\red{3}号点不动

警察从1\red{1}号到2\red{2}号点

小偷在3\red{3}号点不动

警察从2\red{2}号到3\red{3}号点

总共过了4\red{4}次抓到的

样例2\red{2}解释

图二:

img

小偷从2\red{2}号到3\red{3}号点

警察从1\red{1}号到2\red{2}号点

小偷从3\red{3}号到4\red{4}号点

警察从2\red{2}号到3\red{3}号点

小偷在4\red{4}号点不动

警察从3\red{3}号到4\red{4}号点

总共过了6\red{6}次抓到的

20%\red{20\%}的数据 n<=10\red{n<=10}

40%\red{40\%}的数据 n<=100\red{n<=100}

50%\red{50\%}的数据 n<=20000\red{n<=20000}

100%\red{100\%}的数据 n<=200000\red{n<=200000}

2022年小云雀c++初中组重现

未参加
状态
已结束
规则
IOI
题目
5
开始于
2023-4-10 18:00
结束于
2023-4-12 0:00
持续时间
30 小时
主持人
参赛人数
192