其实这道题不用二分去找分界点也能过的说。
所以也用不着树链剖分了。
只要每次改到当前颜色与原来是一样的停止即可。
然后代码贼简单。
#include<bits/stdc++.h> #define LL long long #define re register #define INF 2100000000 #define N 100003 #define mod 1000000007 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } struct EDGE{ int nextt,to; }w[N*2]; struct point{ int col,white,black,gray; }p[N]; int head[N],tot=0; int fa[N],son[N],siz[N]; int ans[5]; void add(int a,int b) { tot++; w[tot].nextt=head[a]; w[tot].to=b; head[a]=tot; } int n,m; void dfs(int x) { siz[x]=0; for(int i=head[x];i;i=w[i].nextt) { int v=w[i].to; if(v==fa[x])continue; dfs(v); siz[x]++; if(p[v].col==1)p[x].black++; else if(p[v].col==0)p[x].white++; else p[x].gray++; } if(!son[x]) { ans[p[x].col]++; return; } if(p[x].black==siz[x])p[x].col=1,ans[1]++; else if(p[x].white==siz[x])p[x].col=0,ans[0]++; else p[x].col=2,ans[2]++; } void update(int x,int now,int before) { if(x==0)return; if(before==1)p[x].black--; else if(before==0)p[x].white--; else p[x].gray--; if(now==1)p[x].black++; else if(now==0)p[x].white++; else p[x].gray++; int tmp=p[x].col; if(p[x].black==siz[x])p[x].col=1; else if(p[x].white==siz[x])p[x].col=0; else p[x].col=2; if(p[x].col==tmp)return; ans[tmp]--;ans[p[x].col]++; update(fa[x],p[x].col,tmp); } int main() { int rt; n=read();m=read(); for(int i=1;i<=n;++i) { fa[i]=read(); if(fa[i]==0)rt=i; add(fa[i],i);add(i,fa[i]); son[fa[i]]++; } for(int i=1;i<=n;++i)p[i].col=read(); dfs(rt); for(int i=1;i<=m;++i) { int x=read(); int col=p[x].col; ans[col]--;ans[col^1]++; p[x].col=col^1; update(fa[x],col^1,col); printf("%d %d %d ",ans[1],ans[0],ans[2]); } }