CF633F The Chocolate Spree

Alice 和 Bob 共有一棵树（无向、无环、连通图）。在树的第 $i$ 个顶点上有 $a_{i}$ 颗等待领取的巧克力。首先，他们各自选择一个不同的顶点作为起点（Alice 先选），并拿走该点上的全部巧克力。 之后，他们轮流行动，每次可以选择一个顶点并收集该节点上的所有巧克力。为了增加趣味性，他们规定一人只能选择在上一次自己选择的顶点相邻且尚未被两人选择过的顶点。 如果在某个时刻某人无法选择满足所有规则的顶点，则该人会跳过自己的回合，直到轮到其能够选择为止。这个过程一直持续到两人都无法继续选择为止。 由于对巧克力的渴望，他们希望收集尽可能多的巧克力。但由于是朋友，他们只在意两人合计能获得多少巧克力。请问他们最多能合计获得多少巧克力？

第一行包含一个整数 $n$（$2 \leq n \leq 100000$），表示树的顶点数。 第二行包含 $n$ 个整数 $a_{i}$（$1 \leq a_{i} \leq 10^{9}$），表示第 $i$ 个节点上存放的巧克力数。 接下来 $n-1$ 行，每行包含两个整数 $u_{i}$ 和 $v_{i}$（$1 \leq u_{i}, v_{i} \leq n$），表示第 $i$ 条边连接了顶点 $u_{i}$ 和 $v_{i}$。

输出 Alice 和 Bob 最多能合计获得的巧克力数。

在第一个样例中，Alice 可以选择顶点 $9$ 开始，Bob 选择顶点 $8$。Alice 会选择顶点 $1$，Bob 无法继续选择。然后 Alice 选择顶点 $7$，两人都无法继续行动。 在第二个样例中，两人会交替地取走每个节点的巧克力。 由 ChatGPT 5 翻译