“吃掉一只海狸,拯救一棵树!” ——这将是比弗利山生态学家紧急会议的座右铭。
重点是地球上海狸的数量已经达到了令人难以置信的规模!他们的数量每天都在增加数倍,他们甚至没有意识到他们对树木的不健康的痴迷对自然和人类造成了多大的伤害。大气中的氧气含量已降至 17%,正如世界上最聪明的人所认为的那样,这还不是结束。
上世纪50年代中期,一群苏联科学家成功预见了海狸的情况,并制定了一项清洁领土的秘密技术。该技术有一个神秘的名称“Beavermuncher-0xFF”。现在,地球的命运落在了一小群为科学奉献一生的人脆弱的肩膀上。
原型已经准备好了,现在需要紧急在实践中进行实验。
你有一棵树,完全被海狸占据。树是无环的连通无向图。该树由 n 个顶点组成,第 i 个顶点包含 ki 个海狸。
“Beavermuncher-0xFF”的工作原理如下:在某个顶点 u 处,如果它们通过边连接,它可以前往顶点 v,并且恰好吃掉位于顶点 v 的一只海狸。如果 v 中没有剩余海狸,则不可能移动到顶点 v。“Beavermuncher-0xFF”不能只是站在某个顶点并吃掉其中的海狸。 “Beavermuncher-0xFF”必须不间断地移动。
为什么“Beavermuncher-0xFF”会这样工作?因为开发人员没有为电池提供空间,而吃掉海狸是将海狸的质量转化为纯能量的必要条件。
可以肯定的是,海狸会对所发生的事情感到震惊,这就是为什么它们无法从树的一个顶点移动到另一个顶点。至于“Beavermuncher-0xFF”,在满足上述条件的情况下,它可以沿着每个边缘双向移动。
树的根位于顶点 s 处。这意味着“Beavermuncher-0xFF”在顶点 s 开始其任务,并且在实验结束时它必须返回那里,因为没有人会把它从高处拿下来。
确定海狸“Beavermuncher-0xFF”可以进食并返回起始顶点的最大数量。
输入
第一行包含整数 n — 树中的顶点数 (1 ≤ n ≤ 105)。第二行包含 n 个整数 ki (1 ≤ ki ≤ 105) — 相应顶点上的海狸数量。接下来的 n - 1 行描述了这棵树。每行包含两个由空格分隔的整数。这些整数表示由边连接的两个顶点。顶点编号为 1 到 n。最后一行包含整数 s — 起始顶点的编号 (1 ≤ s ≤ n)。
输出
打印“Beavermuncher-0xFF”咀嚼的海狸的最大数量。
请不要使用 %lld 说明符在 C++ 中写入 64 位整数。最好使用 cout (也可以使用 %I64d)。
示例
输入 #1
5 1 3 1 3 2 2 5 3 4 4 5 1 5 4
输出 #1
6
输入 #2
3 2 1 1 3 2 1 2 3
输出 #2
2