#P7231. [2023省队模拟]垃圾分类

    ID: 7065 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-树链剖分FHQ Treap 分裂合并标记复合

[2023省队模拟]垃圾分类

题目描述

垃圾分类器由 nn 个垃圾桶和 n−1n-1 条双向传送带组成,形成一棵树。垃圾桶编号为 1,2,…,n1,2,\ldots,n。每条传送带可以花 11 秒把垃圾从一端的垃圾桶送到另一端。投放点是编号为 rr 的垃圾桶。

垃圾也有 nn 种,编号为 1,2,…,n1,2,\ldots,n。第 ii 种垃圾被投到垃圾桶 rr 后,会自动沿最短路径传送到垃圾桶 ii。到达垃圾桶 ii 后,还需要 aia_i 秒才能处理完成。在处理期间,这件垃圾会占住该垃圾桶,挡住需要经过它的其他垃圾。

p6pou 按编号从小到大依次投放每一种垃圾。投放一种垃圾后,必须等它离开垃圾桶 rr,或在垃圾桶 rr 内处理完,才能继续投放下一种。传送也有相同的限制:若垃圾要从垃圾桶 xx 传送到垃圾桶 yy,但此时 yy 中有另一种垃圾,则必须等另一种垃圾离开 yy 或处理完毕后,才能开始这次传送。

求从开始投放到所有垃圾处理完毕所需的总时间。

输入格式

第一行两个整数 n,rn,r,表示垃圾桶的数量和投放点的编号。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

接下来 n−1n-1 行,每行两个整数 x,yx,y,表示连接垃圾桶 x,yx,y 的一条双向传送带。

输出格式

输出一个整数,表示总时间。

样例输入 1

3 2
5 2 5
1 2
1 3

样例输出 1

14

第 22 秒时,11 号垃圾到达 11 号桶,22 号垃圾到达 22 号桶。第 44 秒时,22 号垃圾处理完。第 55 秒时,33 号垃圾到达 22 号桶,由于 11 号桶仍被占用,必须等待。第 77 秒时,11 号垃圾处理完。第 99 秒时,33 号垃圾到达 33 号桶,第 1414 秒处理完成。

样例输入 2

6 4
6 5 4 3 2 1
1 2
3 2
2 4
5 4
1 6

样例输出 2

18

各类垃圾的处理完成时刻依次为 9,8,14,12,16,189,8,14,12,16,18 秒。样例 3 见原附加样例文件。

数据范围与约定

对于 20%20\% 的数据,n≤100n\le100。对于 40%40\% 的数据,n≤1000n\le1000。

对于另外 20%20\% 的数据,树为一条链且垃圾投放点为链的一个端点。对于另外 20%20\% 的数据,所有 aia_i 相等。

对于所有数据,n≤100000n\le100000,0≤ai≤1090\le a_i\le10^9,1≤x,y≤n1\le x,y\le n。