题目翻译

给定一棵 $n$ 个节点的数，$c_i=1$ 表示这个点为黑色，$c_i=0$ 表示这个点为白色。

接下来有 $q$ 次询问，每次给定一个 $u$，把 $u$ 的颜色取反（即黑变白，白变黑），问黑色点是否构成一条链。

题目思路

$k$ 个黑点，构成长度为 $k$ 的链的充要条件是，恰好存在 $k-2$ 个点的度数为 $2$。当然 $k\leq 2$ 需要特判一手。$0$ 个黑点不为链，$1$ 个为链，$2$ 个判断是否相邻。

因此，我们可以得到一个很暴力的做法就是每次维护 $deg_i$ 表示 $i$ 的度数，然后加点删点直接对 $deg_v\gets deg_v-1$。其中 $v$ 是 $u$ 的父亲或者 $u$ 的儿子。

每个点父亲唯一，儿子可能有很多，直接暴力不可取。因此，我们只要一个东西可以快速处理儿子的加减操作即可。

考虑维护 BFS 序。

这样就很容易连续维护自己儿子的贡献。

那么我们直接上线段树，维护『区间加法』，『全局最大值』，『全局最大值出现次数』这三个东西即可。

『全局最大值』和『全局最大值出现次数』是可以直接找根节点信息得到的。

这个是好维护的。

但是这样容易导致我们算进去白点的度数，为了处理这个，我们把白点的度数一开始全设置为 $-\inf$ 即可。每次改成黑点就加上一个 $\inf$。

多测要清空。多清空一点。最后五分钟吃一发 WA on 7 因为清空不到位。

完整代码

不是，哥们？我咋写了 $4.7\ \text{kb}$？

const int inf = 1e9;
int n, q;
vector<int> a[200020];
int c[200020];
int dfn[200020];
bool vis[200020];
int par[200020];
int L[200020];
int R[200020];
struct SegTree
{
    struct node
    {
        int mx, cnt, lzy;
    } t[200020 << 2];
#define ls id << 1
#define rs id << 1 | 1
    void push_up(int id)
    {
        t[id].mx = max(t[ls].mx, t[rs].mx);
        if (t[ls].mx == t[rs].mx)
            t[id].cnt = t[ls].cnt + t[rs].cnt;
        else if (t[ls].mx > t[rs].mx)
            t[id].cnt = t[ls].cnt;
        else
            t[id].cnt = t[rs].cnt;
    }
    void push_down(int id, int l, int r)
    {
        t[ls].mx += t[id].lzy;
        t[rs].mx += t[id].lzy;
        t[ls].lzy += t[id].lzy;
        t[rs].lzy += t[id].lzy;
        t[id].lzy = 0;
    }
    void build(int id = 1, int l = 1, int r = n)
    {
        if (l == r)
            return t[id].mx = t[id].lzy = 0, t[id].cnt = 1, void();
        int mid = l + r >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        push_up(id);
    }
    void clear(int m)
    {
        for (int i = 1; i <= m << 2; i++)
            t[i].mx = t[i].cnt = t[i].lzy = 0;
    }
    void add(int ql, int qr, int k, int id = 1, int l = 1, int r = n)
    {
        if (r < ql || l > qr)
            return;
        if (ql <= l && r <= qr)
            return t[id].mx += k, t[id].lzy += k, void();
        push_down(id, l, r);
        int mid = l + r >> 1;
        add(ql, qr, k, ls, l, mid);
        add(ql, qr, k, rs, mid + 1, r);
        push_up(id);
    }
} T;
void bfs()
{
    int times = 0;
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        dfn[u] = ++times;
        chkmn(L[par[u]], dfn[u]);
        chkmx(R[par[u]], dfn[u]);
        for (int v : a[u])
            if (!vis[v])
                par[v] = u, q.push(v), vis[v] = 1;
    }
}
void solve()
{
    read(n, q);
    for (int i = 1; i <= n; i++)
        dfn[i] = R[i] = par[i] = 0, L[i] = inf, a[i].clear();
    for (int i = 1; i <= n; i++)
        read(c[i]);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        read(u, v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    bfs();
    T.build();
    // for (int i = 1; i <= n; i++)
    //     cout << dfn[i] << " ";
    // cout << endl;
    // for (int i = 1; i <= n; i++)
    //     cout << L[i] << " " << R[i] << endl;
    int black = 0;
    set<int> blk;
    for (int i = 1; i <= n; i++)
    {
        T.add(dfn[i], dfn[i], -inf);
        if (c[i])
        {
            int u = i;
            black++;
            blk.insert(u);
            T.add(dfn[u], dfn[u], inf);
            T.add(dfn[par[u]], dfn[par[u]], 1);
            if (L[u] <= R[u])
                T.add(L[u], R[u], 1);
        }
    }
    while (q--)
    {
        int u;
        read(u);
        if (c[u])
        {
            black--;
            blk.erase(u);
            T.add(dfn[u], dfn[u], -inf);
            T.add(dfn[par[u]], dfn[par[u]], -1);
            if (L[u] <= R[u])
                T.add(L[u], R[u], -1);
            c[u] = 0;
        }
        else
        {
            black++;
            blk.insert(u);
            T.add(dfn[u], dfn[u], inf);
            T.add(dfn[par[u]], dfn[par[u]], 1);
            if (L[u] <= R[u])
                T.add(L[u], R[u], 1);
            c[u] = 1;
        }
        if (!black)
        {
            puts("No");
            continue;
        }
        if (black == 1)
        {
            puts("Yes");
            continue;
        }
        if (black == 2)
        {
            int uu = *blk.begin();
            int vv = *--blk.end();
            puts(par[uu] == vv || par[vv] == uu ? "Yes" : "No");
            continue;
        }
        // cout << T.t[1].mx << " " << T.t[1].cnt << endl;
        if (T.t[1].mx == 2 && T.t[1].cnt == black - 2)
            puts("Yes");
        else
            puts("No");
    }
    T.clear(n + 5);
}