1011. K. Union MEX

题目描述

题目描述

给定一棵包含 (n) 个点的树 (G)，第 (u) 个点有点权 (a_u\in{0,1})。

有 (q) 次询问。每次询问给出一个点 (r)。

对于这次询问，考虑所有满足以下条件的点集 (S)：

• (r\in S)；
• (S) 连通。

记所有这些点集的点权和组成的集合为：

$$V_r= \left\{ \sum_{u\in S}a_u \;\middle|\; r\in S,\ S\text{ 连通} \right\}.$$

求：

$$\operatorname{mex}V_r.$$

一个非负整数集合的 (\operatorname{mex}) 是没有出现在集合中的最小非负整数。例如，集合({0,1,3}) 的 (\operatorname{mex}) 为 (2)。

数据范围

• (1\le T\le3)
• (1\le n,q\le10^5)
• (a_u\in{0,1})
• (1\le r\le n)
• 输入图是一棵树

输入格式

输入包含多组测试数据。第一行包含一个整数 (T)（(1\le T\le3)），表示测试数据组数。

对于每组测试数据：

第一行包含两个整数 (n,q)（(1\le n,q\le10^5)）。

第二行包含 (n) 个整数 (a_1,a_2,\ldots,a_n)（(a_u\in{0,1})）。

接下来 (n-1) 行，每行包含两个整数 (u,v)（(1\le u,v\le n)），表示树上的一条边。

接下来 (q) 行，每行包含一个整数 (r)（(1\le r\le n)），表示一次询问。

保证给出的图是一棵树。

输出格式

对于每次询问，输出一行一个整数，表示答案。

样例输入

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

样例输出

0
3
0
3
3

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1011