题目描述

​A 城是一座新兴城市，城里开设了 $n$ 座工厂，分属 $k$ 家单位（有的单位可能没有工厂），其中第 $i$ 座工厂属于第 $c_i$ 家单位。

​目前，A城的城内有 $n-1$ 条道路，每条道路的两端是不同的工厂。如果将工厂视作图的点，道路视作图的边，那么这张图是树。

​现在A城决定开通该城的前两条公交线路。目前已经决定了：

​$\bullet$ 每条公交线路将连接两座不同的工厂，且两座工厂属于同一单位。

​$\bullet$ 每条公交线路在现有道路上行驶，且往返的路线是一致的。

​$\bullet$ 一条公交线路不会重复经过同一座工厂，两条线路也不会经过同一座工厂。

​我们认为：仅仅将某条公交线路的上行、下行方向互换，得到的是本质相同的线路；将两条公交线路互换，得到的也是本质相同的一组方案。

​在公交线路的运行过程中，有可能某座工厂由于临时施工，不适合作为公交线路的首末站。不过两座工厂不会同时临时施工。

​现在，A城学生算法竞赛协会悬赏 $100$ 分，请你对于平时和 $m$ 次工厂临时施工的情况，分别求出开通公交线路的方案数。

输入格式

​第一行三个正整数 $n, m, k$。

​第二行 $n$ 个数 $c_i$ 表示工厂所属的单位。

​接下来 $n - 1$ 行每行两个数 $a_i, b_i$, 表示有一条道路连接第 $a_i, b_i$ 座工厂。

​接下来 $m$ 行每行一个数 $q_i$，表示第 $i$ 次是第 $q_i$ 座工厂临时施工。

输出格式

​第一行表示平时情况的方案数。

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

6 6 2
2 1 2 1 2 2
1 2
1 3
2 4
2 5
2 6
1
2
3
4
5
6

2
0
1
0
1
1
1

数据规模与约定

​对于所有数据，$m ≤ n ≤ 10^5, c_i ≤ k ≤ n$。

大样例

大样例下载