CF77C Beavermuncher-0xFF

“吃一只河狸，救一棵树！”——这将是生态学家在比弗利山紧急会议上的口号。 事情的起因在于，地球上的河狸数量已经达到了惊人的规模！每天它们的数量都会增长数倍，而它们甚至没有意识到，这种对树木病态的沉迷对自然和人类造成了多么大的危害。大气中的氧气含量已经下降到 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”最多可以吃掉的河狸数量。

由 ChatGPT 5 翻译