题目描述

给定一棵有根树 $T$，包含 $n$ 个顶点和 $n-1$ 条有向边。

对于顶点 $i$，其权值为 $a_i$。如果存在一条从顶点 $y$ 出发、到顶点 $x$ 结束的路径，且该路径仅通过有向边，则称顶点 $x$ 可以从顶点 $y$ 到达。保证所有顶点都可以从根节点到达。

给定 $m$ 对顶点 $(u_i, v_i)$，满足在原树中 $u_i$ 可以从 $v_i$ 到达。现在，将添加新的有向边 $u_i \to v_i$ 以形成一个新的图。

定义一个顶点集合的子集 $S$（可以为空）为 神奇 的，当且仅当对于 $S$ 中的每个元素 $x$，在新图中所有可从 $x$ 到达的顶点都在 $S$ 中。神奇 集合 $S$ 的权值定义为 $S$ 中所有元素的权值之和。空集的权值为 $0$。

对于所有 神奇 集合，共有多少种不同的权值出现？

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 10^4$），表示树 $T$ 的顶点数量。

第二行包含 $n$ 个整数，第 $i$ 个数表示 $a_i$（$0 \leq a_i \leq \sum_{i=1}^{n} a_i \leq 10^4$）。

接下来的 $n-1$ 行描述树的所有 $n-1$ 条有向边。对于第 $i$ 行，给出两个整数 $U_i, V_i$（$1 \leq U_i, V_i \leq n$），表示存在一条从 $U_i$ 指向 $V_i$ 的边。

接下来一行包含一个整数 $m$（$1 \leq m \leq 5 \times 10^5$），表示新增边的数量。

接下来的 $m$ 行描述所有新增的有向边。对于第 $i$ 行，给出两个整数 $u_i, v_i$（$1 \leq u_i, v_i \leq n$），表示新增一条从 $u_i$ 指向 $v_i$ 的边。

• 新增的边 $(u_i, v_i)$ 不 保证两两不同。
• 新增的边 不 保证 $u_i \neq v_i$。
• 树的根节点 未 直接给出。

输出格式

一个整数，表示上述问题的答案。

3
1 2 3
1 3
1 2
1
2 1

3

解释 #1

样例包含三个 神奇 集合：$\{1, 2, 3\}、\{3\}、\emptyset$。由于它们的权值互不相同，答案为 $3$。