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

题目描述

“吃一只河狸，救一棵树！”——这将是生态学家在比弗利山紧急会议上的口号。

事情的起因在于，地球上的河狸数量已经达到了惊人的规模！每天它们的数量都会增长数倍，而它们甚至没有意识到，这种对树木病态的沉迷对自然和人类造成了多么大的危害。大气中的氧气含量已经下降到 17％，而世界上的顶尖科学家认为，这还不是终点。

上个世纪 50 年代中期，一组苏联科学家预见到了河狸泛滥的局面，并研发出了一项神秘的土地净化技术。这项技术被赋予了神秘的名字“Beavermuncher-0xFF”。现在，地球的命运掌握在一小群为科学献身的人的脆弱肩膀上。

原型机已经准备就绪，现在需要紧急开展实地实验。

你得到了一棵完全被河狸占据的树。树是一种无环联通无向图，包含 $n$ 个顶点，第 $i$ 个顶点上有 $k_i$ 只河狸。

“Beavermuncher-0xFF”的工作原理如下：它位于某个顶点 $u$ 时，可以沿着边移动到与之直接相连的顶点 $v$，并在 $v$ 吃掉正好一只河狸。如果 $v$ 这个顶点上已经没有河狸，则无法移动到 $v$。注意，“Beavermuncher-0xFF”无法原地吃掉自己所在顶点上的河狸，必须不断移动，不能停留。

为什么“Beavermuncher-0xFF”要这样工作？因为开发者没有为它设计电池舱，只能通过吃河狸将其体重转化为纯能量来行动。

可以保证河狸会因突发状况而惊呆，不会主动从一个顶点跑到另一个顶点。而“Beavermuncher-0xFF”可以在满足上述条件下，自由地在每条边的两端之间双向移动。

树的根节点为 $s$，即“Beavermuncher-0xFF”从顶点 $s$ 开始任务，且实验结束后必须返回到起点 $s$，因为没人愿意把它从高处取下来。

请你求出“Beavermuncher-0xFF”在满足上述规则且能回到起点 $s$ 的前提下，最多能吃掉多少只河狸。

输入格式

第一行包含整数 $n$，表示树的顶点数（$1 \leq n \leq 10^5$）。
第二行包含 $n$ 个整数 $k_i$（$1 \leq k_i \leq 10^5$），表示每个顶点上的河狸数量。
接下来的 $n-1$ 行，每行包含两个用空格分隔的整数，表示树中的一条边，连接编号为 $1$ 到 $n$ 的两个顶点。
最后一行包含整数 $s$，表示起始顶点编号（$1 \leq s \leq n$）。

输出格式

输出“Beavermuncher-0xFF”最多可以吃掉的河狸数量。

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

6

3
2 1 1
3 2
1 2
3

2