T141409 「Beta2020」堡垒

lzqy 掌握着许多堡垒。现在 ta 要向其他的堡垒抽调兵力，来增强主司令堡垒的兵力。你能帮 ta 算算主司令堡垒能获得多少兵力吗？

lzqy 掌握着 $n$ 个堡垒，这些堡垒互相由驿道连接。 如果把所有的堡垒看作一棵树，那么根节点就是主司令堡垒（一号堡垒），父节点是其子节点的上司堡垒，子节点是其父节点的下属堡垒。一开始只有叶节点上的堡垒有无限的兵力，其他堡垒皆无兵力。 有若干个堡垒的出兵会有如下的要求（**一种或多种，所有在叶节点上的堡垒一定会有如下要求**）： - `1 u` 每一次出兵数量不得大于 $u$（ $1\leq u\leq k$ ）。 - `2 u v` 每一次出兵数量不得大于 $u$ 且要是 $v$ 的倍数，其中 （$1\le v

第一行有两个正整数，$n,m,k$，其中 $m$ 代表有多少个特殊要求（有特殊要求的堡垒包括所有叶节点上的堡垒）； 接下来 $n-1$ 行，每行两个数 $u,v$，代表 $u$ 号堡垒与 $v$ 号堡垒有上下属关系。 接下来 $m$ 行，每行第一个数 $j(2\leq j\leq n)$，表示 $j$ 号堡垒有出兵要求。然后按照上述格式给出出兵要求。

一行一个整数，即主司令堡垒可以获得的兵力。

### 样例一解释 一开始，所有节点出兵要求如图：  可以发现，四号节点有一种出兵方式（不能总兵力为$0$），五号节点有$5$种出兵方式，则二号节点获得$1$个兵，三号节点获得$5$个兵，如图：  此时，二号节点与三号节点的兵力搭配方式有： $\{0,2\}\{0,4\}\{1,0\}\{1,2\}\{1,4\}$ 共五种，故答案为 $5$。 ### 数据范围与约定 | Subtask | 数据范围 | 分值 | | :-----------: |:-----------: | :-----------: | | Subtask0 | $1\le n\le 16,1\leq m\le 4n,1\leq k\leq32768$ | $10$ | | Subtask1 | $1\le n\le 256,1\leq m\le 4n,1\leq k\leq32768$ | $20$ | | Subtask2 | $1\leq n\leq 1024,1\leq m \leq 4n,1\leq k\leq32768$ | $70$ |