CF1975E.Chain Queries

给定一棵有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。初始时，每个顶点被染成白色或黑色。

你需要进行 $q$ 次操作：

• “u” —— 翻转顶点 $u$ 的颜色（如果原来是白色，则变为黑色；如果原来是黑色，则变为白色）。

每次操作后，你需要回答所有黑色顶点是否构成一条链。也就是说，是否存在两个黑色顶点，使得它们之间的简单路径经过且仅经过所有黑色顶点。特别地，如果只有一个黑色顶点，也视为构成一条链。如果没有黑色顶点，则不构成链。

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1\leq t\leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1\leq n,q\leq 2\cdot 10^5$）。

第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$（$c_i\in\{\mathtt{0},\mathtt{1}\}$），表示每个顶点的初始颜色。$c_i$ 表示顶点 $i$ 的颜色，$\mathtt{0}$ 表示白色，$\mathtt{1}$ 表示黑色。

接下来 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1\leq x_i,y_i\leq n$），表示在顶点 $x_i$ 和 $y_i$ 之间有一条边。保证这些边构成一棵树。

接下来的 $q$ 行，每行包含一个整数 $u_i$（$1\leq u_i\leq n$），表示需要翻转顶点 $u_i$ 的颜色。

保证所有测试用例中 $n$ 和 $q$ 的总和分别不超过 $2\cdot 10^5$。

对于每次操作，如果黑色顶点构成一条链，输出 “Yes”；否则输出 “No”。

你可以用任意大小写组合输出 “Yes” 和 “No”（例如 "yEs"、"yes"、"Yes"、"YES" 都被认为是肯定回答）。

在第二个测试用例中，顶点的颜色变化如下：

初始树：

第一次操作翻转顶点 $4$ 的颜色：

第二次操作翻转顶点 $3$ 的颜色：

第三次操作翻转顶点 $2$ 的颜色：

第四次操作翻转顶点 $5$ 的颜色：

由 ChatGPT 4.1 翻译