题意
给定一棵 \(n\) 个结点的树，第 \(i\) 个点有颜色 \(c_i\)，其中 \(c_i=0\) 为白色，\(c_i=1\) 为黑色。有 \(q\) 次询问，每次询问给定一个正整数 \(u\)，要求将结点 \(u\) 的颜色反转，并判断修改后的树上的所有黑点是否构成一条链。询问不独立。
思路
-
由于这是一棵树，一个点只有一个父亲，所以当我们修改某个点的颜色时，我们可以很容易的维护与该点父亲有关的信息，但我们如果挨个修改其儿子的信息则会超时，因此在接下来关于判断黑点是否构成链的条件时，我们应该判断那些容易维护的信息。
-
首先，如果树上的黑点构成一条链，那他们必须是联通的。观察可得，一个黑点的连通块中有且只有一个点的父亲（即该块中所有黑点的公共祖先）不是黑色。因此如果构成链，则树上只有一个黑点父亲不是黑点。
-
其次，如果构成链，则不能有黑点与 \(2\) 个或更多黑点相连。分两种情况讨论：一是父亲为黑点且拥有 \(2\) 个或更多黑色儿子，二是父亲不为黑点但拥有 \(3\) 个或更多黑色儿子。因此我们可以统计有 \(2\) 个黑色儿子的黑色点数量和有 \(3\) 个黑色儿子的黑色点数量，如果构成链，则前者不大于 \(1\)，若等于 \(1\) 则该点父亲必须不为黑色；后者等于 \(0\)。
代码
#include<bits/stdc++.h>
#define int long long
#define MAXN 400005
using namespace std;
int T,n,qq,cnt,head[MAXN],c[MAXN],a[MAXN],cnta,cntb,cntc,b[MAXN],fa[MAXN];
queue<int>q;
struct Edge{int value,next;
}edge[MAXN];
void addedge(int u,int v){edge[++cnt].value=v;edge[cnt].next=head[u];head[u]=cnt;
}
void dfs(int x,int father){fa[x]=father;if(c[x]==1)a[fa[x]]++;if(c[x]==1&&c[fa[x]]==0)cnta++;for(int i=head[x];i;i=edge[i].next){int y=edge[i].value;if(y!=fa[x]){dfs(y,x);}}if(c[x]==1){if(a[x]==2){cntc++;b[x]=1;q.push(x);}else if(a[x]>2){cntb++;}}
}
signed main(){scanf("%lld",&T);while(T--){scanf("%lld%lld",&n,&qq);while(!q.empty())q.pop();cnt=cnta=cntb=cntc=0;//cnta表示父亲不是黑色的黑色点数量//cntb表示有3个或更多黑色儿子的黑色点数量//cntc表示有2个黑色儿子的黑色点数量 for(int i=1;i<=n*2;i++){edge[i]=(Edge){0,0};head[i]=c[i]=b[i]=a[i]=0;}for(int i=1;i<=n;i++){scanf("%lld",&c[i]);}for(int i=1;i<n;i++){int u,v;scanf("%lld%lld",&u,&v);addedge(u,v);addedge(v,u);}dfs(1,0);fa[n+1]=n+1;c[n+1]=0;for(int i=1;i<=qq;i++){int x;scanf("%lld",&x);if(c[x]==1){if(c[fa[x]]==0)cnta--;cnta+=a[x];if(a[x]>=3)cntb--;if(a[fa[x]]==3&&c[fa[x]]==1){cntb--;cntc++;b[fa[x]]=1;q.push(fa[x]);}if(a[x]==2){cntc--;b[x]=0;}if(a[fa[x]]==2&&c[fa[x]]==1){cntc--;b[fa[x]]=0;}c[x]=0;a[fa[x]]--;}else{if(c[fa[x]]==0)cnta++;cnta-=a[x];if(a[x]>=3)cntb++;if(a[fa[x]]==2&&c[fa[x]]==1){cntb++;cntc--;b[fa[x]]=0;}if(a[x]==2){cntc++;b[x]=1;q.push(x);}if(a[fa[x]]==1&&c[fa[x]]==1){cntc++;b[fa[x]]=1;q.push(fa[x]);}c[x]=1;a[fa[x]]++;}int tmp=n+1;if(!q.empty()){tmp=q.front();while(!b[tmp]){q.pop();if(q.empty())break;tmp=q.front();}}//若构成链，则cnta==1且cntb==0且cntc<=1且若cntc等于一，该点父亲不为黑色 if(cnta!=1||cntb>0||cntc>1||(cntc==1&&c[fa[tmp]]==1))printf("No\n");else printf("Yes\n");}}return 0;
}