U161443 [NOI2021SDPTTest5]平凡

甲城是一座新兴城市，城里开设了 $n$ 座工厂，分属 $k$ 家单位（有的单位可能没有工厂），其中第 $i$ 座工厂属于第 $c_i$ 家单位。 目前，甲城的路网还相当不发达。城内有 $n-1$ 条道路，每条道路的两端是不同的工厂。如果将工厂视作图的点，道路视作图的边，那么这张图是树。 现在甲城决定开通该城的前两条公交线路。目前已经决定了： 1. 每条公交线路将连接两座不同的工厂，且两座工厂属于同一单位。 2. 每条公交线路在现有道路上行驶，且往返的路线是一致的。 3. 一条公交线路不会重复经过同一座工厂，两条线路也不会经过同一座工厂。 我们认为：仅仅将某条公交线路的上行、下行方向互换，得到的是本质相同的线路。 将两条公交线路互换，得到的也是本质相同的一组方案。 在公交线路的运行过程中，有可能某座工厂由于临时施工，不适合作为公交线路的首末站。不过两座工厂不会同时临时施工。 现在，甲城学生算法竞赛协会悬赏 $100$ 分，请你对于平时和 $m$ 次工厂临时施工的情况，分别求出开通公交线路的方案数。

第一行三个正整数 $n, m, k$。 第二行 $n$ 个数 $c_i$ 表示工厂所属的单位。 接下来 $n-1$ 行每行两个数 $a_i, b_i$, 表示有一条道路连接第 $a_i, b_i$ 座工厂。 接下来 $m$ 行每行一个数 $k_i$, 表示第 $i$ 次是第 $q_i$ 座工厂临时施工。

第一行表示平时情况的方案数。 接下来 $m$ 行分别表示各次询问情况下的方案数。

对于 $10\%$ 的数据，$n\leq 50$； 对于另外 $15\%$ 的数据，$n\leq 10^4,k=1$。其中，存在 $5\%$ 的数据满足 $n\leq 10^3$，存在 $5\%$ 的数据满足 $m\leq 10$； 对于另外 $15\%$ 的数据，$n\leq 10^4,m=1$。其中，存在 $5\%$ 的数据满足 $n\leq 10^3$； 对于另外 $20\%$ 的数据，$k=2$。其中，存在 $10\%$ 的数据满足 $n\leq 10^4,m\leq 10$； 对于另外 $20\%$ 的数据，$c_{q_i}$ 互不相同。其中，存在 $10\%$ 的数据满足 $n\leq 10^4$； 对于 $100\%$ 的数据，$1\leq m\leq n\leq 10^5,1\leq c_i\leq k\leq n$。