密钥古树

题目描述

在群山深处的“密码档案馆”里，生长着一棵古老的密钥古树。这棵树是一棵普通的二叉树，枝干交错，每个节点上都有天然形成的纹路，纹路只有两种形态，分别记作 0 和 1，即每个节点承载 1 比特的信息。传说，从树根出发，沿着枝干一路抵达叶片的每一条路径，都会形成一段独特的二进制密钥：根节点上的纹路代表密钥的最高位，越靠近叶片，数位越低。例如，若一条路径上的纹路序列为 1 -> 0 -> 1，则它解析出的二进制数为 101，对应的十进制数值为 $5$。

档案馆的守护者需要遍历整棵密钥古树，把所有从根节点到叶子节点的路径所代表的二进制数全部解析出来，并计算它们的数值总和。只有准确求出这个总和，才能打开档案馆最深处的密钥匣。

具体来说，给定一棵密钥古树的节点总数 $n$、每个节点承载的比特值，以及 $n-1$ 条连接节点的边。虽然输入看起来是无向边，但在解析密钥时，我们默认节点 $1$ 为整棵树的根节点，数据流向是从上至下的。请计算所有从根节点到叶子节点的路径所代表的二进制数的总和。题目数据保证，即便在所有路径累加之后，最终结果依然可以被存储在一个标准的 32 位整数中。

输入格式

第一行输入一个整数 $n$ ($1 \leq n \leq 1000$)，表示这棵密钥古树的节点总数。
第二行输入 $n$ 个整数 $v_1, v_2, \dots, v_n$，其中 $v_i$ 表示编号为 $i$ 的节点承载的比特值（$0$ 或 $1$）。
接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间有一条物理链路相连。

注意：节点编号从 $1$ 开始计数。虽然输入看起来是无向边，但在解析密钥时，我们默认节点 $1$ 为整棵树的根节点，数据流向是从上至下的。

输出格式

输出一个整数，表示所有根到叶路径所代表的二进制数的总和。

输入输出样例

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

15

样例解释：
这棵密钥古树的结构如下：

        1
       / \
      1   0
     / \
    1   0

共捕获 3 条有效链路：

1. 链路 1 → 0：解析为 10，数值为 $2$。
2. 链路 1 → 1 → 1：解析为 111，数值为 $7$。
3. 链路 1 → 1 → 0：解析为 110，数值为 $6$。

校验总和为 $2 + 7 + 6 = 15$。