#P7231. [2023省队模拟]垃圾分类
[2023省队模拟]垃圾分类
题目描述
垃圾分类器由 个垃圾桶和 条双向传送带组成,形成一棵树。垃圾桶编号为 。每条传送带可以花 秒把垃圾从一端的垃圾桶送到另一端。投放点是编号为 的垃圾桶。
垃圾也有 种,编号为 。第 种垃圾被投到垃圾桶 后,会自动沿最短路径传送到垃圾桶 。到达垃圾桶 后,还需要 秒才能处理完成。在处理期间,这件垃圾会占住该垃圾桶,挡住需要经过它的其他垃圾。
p6pou 按编号从小到大依次投放每一种垃圾。投放一种垃圾后,必须等它离开垃圾桶 ,或在垃圾桶 内处理完,才能继续投放下一种。传送也有相同的限制:若垃圾要从垃圾桶 传送到垃圾桶 ,但此时 中有另一种垃圾,则必须等另一种垃圾离开 或处理完毕后,才能开始这次传送。
求从开始投放到所有垃圾处理完毕所需的总时间。
输入格式
第一行两个整数 ,表示垃圾桶的数量和投放点的编号。
第二行 个整数 。
接下来 行,每行两个整数 ,表示连接垃圾桶 的一条双向传送带。
输出格式
输出一个整数,表示总时间。
样例输入 1
3 2
5 2 5
1 2
1 3
样例输出 1
14
第 秒时, 号垃圾到达 号桶, 号垃圾到达 号桶。第 秒时, 号垃圾处理完。第 秒时, 号垃圾到达 号桶,由于 号桶仍被占用,必须等待。第 秒时, 号垃圾处理完。第 秒时, 号垃圾到达 号桶,第 秒处理完成。
样例输入 2
6 4
6 5 4 3 2 1
1 2
3 2
2 4
5 4
1 6
样例输出 2
18
各类垃圾的处理完成时刻依次为 秒。样例 3 见原附加样例文件。
数据范围与约定
对于 的数据,。对于 的数据,。
对于另外 的数据,树为一条链且垃圾投放点为链的一个端点。对于另外 的数据,所有 相等。
对于所有数据,,,。