CF77C.Beavermuncher-0xFF

"Eat a beaver, save a tree!" — That will be the motto of ecologists' urgent meeting in Beaverley Hills.

And the whole point is that the population of beavers on the Earth has reached incredible sizes! Each day their number increases in several times and they don't even realize how much their unhealthy obsession with trees harms the nature and the humankind. The amount of oxygen in the atmosphere has dropped to 17 per cent and, as the best minds of the world think, that is not the end.

In the middle of the 50-s of the previous century a group of soviet scientists succeed in foreseeing the situation with beavers and worked out a secret technology to clean territory. The technology bears a mysterious title "Beavermuncher-0xFF". Now the fate of the planet lies on the fragile shoulders of a small group of people who has dedicated their lives to science.

The prototype is ready, you now need to urgently carry out its experiments in practice.

You are given a tree, completely occupied by beavers. A tree is a connected undirected graph without cycles. The tree consists of n vertices, the i-th vertex contains k__i beavers.

"Beavermuncher-0xFF" works by the following principle: being at some vertex u, it can go to the vertex v, if they are connected by an edge, and eat exactly one beaver located at the vertex v. It is impossible to move to the vertex v if there are no beavers left in v. "Beavermuncher-0xFF" cannot just stand at some vertex and eat beavers in it. "Beavermuncher-0xFF" must move without stops.

Why does the "Beavermuncher-0xFF" works like this? Because the developers have not provided place for the battery in it and eating beavers is necessary for converting their mass into pure energy.

It is guaranteed that the beavers will be shocked by what is happening, which is why they will not be able to move from a vertex of the tree to another one. As for the "Beavermuncher-0xFF", it can move along each edge in both directions while conditions described above are fulfilled.

The root of the tree is located at the vertex s. This means that the "Beavermuncher-0xFF" begins its mission at the vertex s and it must return there at the end of experiment, because no one is going to take it down from a high place.

Determine the maximum number of beavers "Beavermuncher-0xFF" can eat and return to the starting vertex.

“吃掉一只海狸，拯救一棵树！”——这将成为生态学家在比弗利山庄召开紧急会议的口号。

问题的核心在于：全球海狸数量已达到惊人的规模！每天其种群数量都会增长数倍，而它们甚至尚未意识到自身对树木病态的痴迷正给自然与人类带来多么严重的危害。目前大气中的氧气含量已骤降至17%，而据全球顶尖智者推测，这还远非最坏情况。

早在上世纪50年代中期，一群苏联科学家便成功预见了海狸泛滥的局面，并秘密研发出一种名为“Beavermuncher-0xFF”的区域清理技术。如今，整个星球的命运，就系于这一小群将毕生奉献给科学的人们那脆弱的肩头。

原型机已准备就绪，现在亟需立即开展实地实验。

你被给定一棵完全被海狸占据的树。所谓树，即一个无环的连通无向图。该树包含 $n$ 个顶点，其中第 $i$ 个顶点上有 $k_i$ 只海狸。

“Beavermuncher-0xFF” 的工作原理如下：当它位于某个顶点 $u$ 时，若 $u$ 与顶点 $v$ 之间存在一条边，则它可以移动到 $v$，并恰好吃掉位于 $v$ 处的一只海狸；若 $v$ 处已无海狸，则无法移向 $v$。“Beavermuncher-0xFF” 不能停留在某个顶点原地进食；它必须持续移动、不可停顿。

为何“Beavermuncher-0xFF” 必须如此运作？因为研发者未为其预留电池空间，而进食海狸是将其质量转化为纯粹能量所必需的过程。

可以保证：海狸将因眼前发生的一切而震惊失措，因此无法从树的一个顶点移动至另一顶点。至于“Beavermuncher-0xFF”，只要满足上述条件，它即可沿任意一条边双向通行。

树的根节点位于顶点 $s$。这意味着“Beavermuncher-0xFF” 从顶点 $s$ 出发执行任务，且实验结束时必须返回 $s$ —— 毕竟没人会爬上高处把它取下来。

请确定“Beavermuncher-0xFF” 在最终返回起始顶点的前提下，最多能吃掉多少只海狸。

The first line contains integer n — the number of vertices in the tree (1 ≤ n ≤ 105). The second line contains n integers k__i (1 ≤ k__i ≤ 105) — amounts of beavers on corresponding vertices. Following n - 1 lines describe the tree. Each line contains two integers separated by space. These integers represent two vertices connected by an edge. Vertices are numbered from 1 to n. The last line contains integer s — the number of the starting vertex (1 ≤ s ≤ n).

第一行包含一个整数 $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$）。

Print the maximum number of beavers munched by the "Beavermuncher-0xFF".

Please, do not use %lld specificator to write 64-bit integers in C++. It is preferred to use cout (also you may use %I64d).

输出“Beavermuncher-0xFF”吃掉的海狸的最大数量。

请注意，在 C++ 中请勿使用 %lld 格式说明符来输出 64 位整数。推荐使用 cout（您也可以使用 %I64d）。