#P17870. [Ontak2019]WIR
[Ontak2019]WIR
— 病毒传播
有 座城市,由 条道路连接成一棵树。最初有 座城市感染病毒。
病毒可以沿道路从一个已感染城市传播到相邻城市,传播一次需要一小时。每个城市在同一时刻最多向一个相邻城市传播病毒;不同城市可以同时传播。一个城市感染完成后,从下一小时起即可向其他城市传播,原来已经感染的城市仍保持感染。
求让全部城市感染所需的最少小时数。传播顺序可以自由安排。
输入格式
第一行两个整数 。
第二行 个两两不同的整数,表示初始感染的城市编号。
接下来 行,每行两个整数 ,表示一条道路。
输出格式
输出一个整数,表示感染全部城市所需的最少小时数。
数据范围
,。城市编号在 内,保证道路构成树。
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | 5 | |
| 2 | 20 | |
| 3 | ||
| 4 | 10 | |
| 5 | 5 | |
| 6 | 30 | |
| 7 | 10 |
原题总约束允许 ,子任务表只列到 ;标程支持总约束中的16个源点。
样例 1
输入:
5 2
2 4
1 2
2 3
3 4
4 5
输出:
2
样例 2
输入:
4 1
1
1 2
1 3
2 4
输出:
2