题解：CF1975E Chain Queries
题意
- 给定一棵
n 个点的树，每个点是黑色或白色的。 - 有
q 次操作，每次操作是反转某个点的颜色（即黑变白，白变黑）。 - 每次操作后，判断树上的所有黑色点是否恰好是一条链。
- 有多测，
\sum n,\sum q\le 2\times 10^5 。
题解
提供一个把脑子扔掉想出来的做法。
首先容易发现黑点组成一个森林。
考虑一个森林是一条链的充要条件是这个森林中只有一个点或没有任何一个点的度数为
前者容易特判，但后者不好维护，原因是一个点的修改会影响它的所有儿子，复杂度能飙到
这时候题解做法是让你只统计每个点儿子的信息来判，就不会有父亲改儿子的情况了。但这个需要动脑子，非常不好。
不动脑子的想法是用数据结构来维护一个点的所有儿子。一个显然的思路是仿照树上差分，构造一个序列使得单次要维护的东西在序列上是连续的。容易想到维护点被 bfs 到的顺序。这样一个点的所有儿子在序列上就是连续的了。
那么就是在线段树上维护上面那坨东西了。容易发现可以维护区间最小值和最小值出现次数，操作就是单点赋值（白色赋为一个充分大的数，黑色赋为该点周围的黑点数）和区间加一减一。都是线段树能维护的简单操作。另外注意每次修改和查询时记得额外考虑父亲。
复杂度
code
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,q,a[N],ff[N];
vector<int> e[N];
int cntd[N],bfn[N],st[N],ed[N],Tm,mp[N];
//st 和 ed 分别是直接儿子在 bfs 序列上的起点和终点。
struct Node{
int mn,cmn;
Node operator +(const Node &r){
Node res;
res.mn=min(mn,r.mn);res.cmn=0;
if(res.mn==mn) res.cmn+=cmn;
if(res.mn==r.mn) res.cmn+=r.cmn;
return res;
}
};
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
Node info[N<<2];
int cbl[N<<2],mark[N<<2];
void PushUp(int id){
cbl[id]=cbl[id<<1]+cbl[id<<1|1];
info[id]=info[id<<1]+info[id<<1|1];
}
void modi(int id,int x){
mark[id]+=x;
info[id].mn+=x;
}
void PushDown(int id){
if(!mark[id]) return;
modi(id<<1,mark[id]);modi(id<<1|1,mark[id]);
mark[id]=0;
}
void Build(int l=1,int r=n,int id=1){
mark[id]=0;//带多测的线段树记得清空懒标记。
if(l==r){
cbl[id]=a[mp[l]];
info[id].cmn=1;
info[id].mn=a[mp[l]]?cntd[mp[l]]:inf;
return;
}
Build(lson);Build(rson);
PushUp(id);
}
void Modify(int L,int R,int X,int l=1,int r=n,int id=1){
if(R<l||r<L) return;
if(L<=l&&r<=R){
modi(id,X);
return;
}
PushDown(id);
if(L<=mid) Modify(L,R,X,lson);
if(mid< R) Modify(L,R,X,rson);
PushUp(id);
}
void Change(int P,int X,int l=1,int r=n,int id=1){
//单点修改。
if(l==r){
info[id].mn=X;
if(X==inf){
cbl[id]=0;
}else{
cbl[id]=1;
}
return;
}
PushDown(id);
if(P<=mid) Change(P,X,lson);
else Change(P,X,rson);
PushUp(id);
}
int Query(int L,int R,int l=1,int r=n,int id=1){
//将白点改成黑点时求周围的黑点数。
if(R<l||r<L) return 0;
if(L<=l&&r<=R){
return cbl[id];
}
PushDown(id);
int res=0;
if(L<=mid) res+=Query(L,R,lson);
if(mid< R) res+=Query(L,R,rson);
return res;
}
bool Ask(){//注意特判只有一个黑点的情况。
return cbl[1]==1||(cbl[1]&&info[1].mn==1&&info[1].cmn==2);
}
}mt;
void bfs(){
queue<int> q;
q.push(1);
Tm=0;
bfn[1]=++Tm;
while(q.size()){
int u=q.front();q.pop();
st[u]=ed[u]=0;
mp[bfn[u]]=u;
for(auto i:e[u]){
if(i==ff[u]) continue;
ff[i]=u;
bfn[i]=++Tm;
if(!st[u]) st[u]=bfn[i];
ed[u]=bfn[i];
q.push(i);
}
}
}
void solve(){
n=read();q=read();
forup(i,1,n){
a[i]=read();
e[i].clear();
cntd[i]=0;
}
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
cntd[u]+=a[v];cntd[v]+=a[u];
}
bfs();
mt.Build();
forup(i,1,q){
int u=read();
mt.Modify(st[u],ed[u],(!a[u])-a[u]);
mt.Modify(bfn[ff[u]],bfn[ff[u]],(!a[u])-a[u]);
if(a[u]){
mt.Change(bfn[u],inf);
}else{
mt.Change(bfn[u],mt.Query(st[u],ed[u])+a[ff[u]]);
}
a[u]^=1;
puts(mt.Ask()?"Yes":"No");
}
}
signed main(){
int t=read();
while(t--){
solve();
}
}