题目描述

园区里有 $n$ 盏灯，编号为 $1,2,\ldots,n$．灯与灯之间有 $n-1$ 条双向通道，这些通道将所有灯连接成一棵树．

第 $i$ 盏灯属于控制组 $c_i$，每盏灯恰好属于一个控制组，分组始终不变．最初，所有灯都处于熄灭状态．

管理员将依次进行 $q$ 次操作．每次操作给出一个组号 $x$，将这个组的所有灯同时切换状态：亮着的灯熄灭，熄灭的灯亮起．如果没有灯属于这个组，本次操作不改变任何灯的状态．

只保留亮着的灯，以及两端都亮着的通道．如果两盏灯能沿着保留下来的通道互相到达，就认为它们属于同一个照明区域．一盏没有与其他亮灯相连的亮灯，也单独构成一个照明区域．如果所有灯都熄灭，照明区域的数量为 $0$．

请在每次操作后，求出照明区域的数量．

输入格式

第一行包含两个整数 $n,q$，分别表示灯的数量和操作次数．

第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示各盏灯所属的控制组．

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示编号为 $u,v$ 的两盏灯之间有一条通道．数据保证给出的通道构成一棵树．

接下来 $q$ 行，每行包含一个整数 $x$，表示本次操作切换的组号．

输出格式

输出 $q$ 行，每行一个整数，依次表示每次操作后的照明区域数量．

样例 1

输入

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

输出

2
2
1
3

解释

第一次操作后，灯 $1,3$ 亮起，它们之间的灯 $2$ 仍然熄灭，因此有两个照明区域．

第二次操作后，灯 $2,5$ 也亮起．灯 $1,2,3$ 构成一个照明区域，灯 $5$ 单独构成一个照明区域．

第三次操作后，所有灯都亮起，只有一个照明区域．第四次操作将灯 $2,5$ 熄灭，剩下的灯 $1,3,4$ 各自构成一个照明区域．

样例 2

输入

3 5
2 2 2
1 2
2 3
1
2
2
3
2

输出

0
1
0
0
1

下发样例

• Data/sample1.in 与 Data/sample1.ans：题面中的样例 1．
• Data/sample2.in 与 Data/sample2.ans：题面中的样例 2．
• Data/sample3.in 与 Data/sample3.ans：$n=q=2000$，满足子任务 1．
• Data/sample4.in 与 Data/sample4.ans：$n=q=10^5$，满足子任务 2．
• Data/sample5.in 与 Data/sample5.ans：$n=q=10^5$，满足子任务 3．
• Data/sample6.in 与 Data/sample6.ans：$n=q=10^5$，满足子任务 4．
• Data/sample7.in 与 Data/sample7.ans：$n=q=10^5$，无特殊限制．
• Data/sample8.in 与 Data/sample8.ans：$n=q=10^5$，无特殊限制．
• Data/sample9.in 与 Data/sample9.ans：$n=q=10^5$，无特殊限制．

点击下载本题选手目录

数据规模与约定

对于所有数据，保证 $1\le n,q\le 10^5$，$1\le c_i,x\le n$，$1\le u,v\le n$，$u\ne v$．输入的所有数均为整数．

对于一个控制组，将恰好有一个端点属于这个组的通道称为该组的外接通道．

本题采用捆绑测试．只有通过一个子任务的全部测试点，才能获得该子任务的分数．

子任务编号	分数	附加限制
1	20	$n,q\le 2000$
2	15	$c_1,c_2,\ldots,c_n$ 中不同的数不超过 $20$ 个
3		所有操作给出的组号两两不同
4		每个控制组的外接通道数量不超过 $30$
5	35	无