题目描述

给定一棵 $n$ 个节点的叶向树，根节点为 $r$。叶向树即该树由 $n-1$ 条有向边构成，每条有向边指向根节点所在的另一端，经过该边所需要的时间均为 $1$。

接下来，将有 $n$ 个人按照编号从小到大的顺序依次空降到根节点 $r$。第 $i$ 个人的目的是到节点 $i$ 完成任务，因此人 $i$ 将沿着叶向树上的唯一路径到达点 $i$，随后在点 $i$ 上停留 $a_i$ 单位时间执行任务，之后人 $i$ 即完成任务。由于有向边的“特殊性”，人们不能在有向边上停留，且仅能在节点上停留整数单位时间。

由于任务的“特殊性”，这些人在进行任务的过程中不能相互干扰，即，正在执行任务的人（不包括已经完成任务的人）不能同一时刻在同一个节点。

也就是说，当人 $i$ 在点 $i$ 处正在执行任务时，若人 $j$ 抵达点 $i$ 的父节点且点 $i$ 是点 $j$ 的必经节点，则人 $j$ 必须在原位等待直到人 $i$ 任务完成。若人 $i$ 在时刻 $t$ 完成任务，则人 $j$ 在时刻 $t$ 可以沿有向边出发并在时刻 $t+1$ 抵达点 $i$。

类似的，若人 $j$ 抵达某点后发现下一个必经节点处有人 $i$ 在等待，则人 $j$ 必须等待人 $i$ 离开该点后才能移动至该点。即若人 $i$ 在时刻 $t$ 决定移动并于时刻 $t+1$ 移动到了其他节点，则人 $j$ 同样可以在时刻 $t$ 沿有向边出发并在时刻 $t+1$ 到达人 $i$ 在时刻 $t$ 所在的节点。

空降过程同理，若人 $i$ 发现人 $i-1$ 由于堵塞而停留在出发点 $r$，则人 $i$ 不会空降（施展魔法在空中悬浮），直到人 $i-1$ 离开点 $r$。

指挥官希望这 $n$ 个人能够在最短时间内完成任务，询问在采用最优策略的情况下这 $n$ 个人都完成任务所需要的最少单位时间。

输入格式

输入的第一行包含两个正整数 $n,r$，表示树的点数和根节点编号。

输入的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示这 $n$ 个人停留在对应节点上执行任务所需要的时间。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$，描述树上的一条边 $(u,v)$。

输出格式

输出的第一行包含一个整数，表示答案。

样例

输入

3 2
5 2 5
1 2
1 3

输出

14

数据范围

对于 $100\%$ 的数据，保证

特殊性质 A：保证给定的树形态为一条链，且出发点 $r$ 为该链的一个端点。

特殊性质 B：保证所有人完成任务所需要的时间均相等，即 $a_1=a_2=\cdots=a_n$。