给定一棵树，维护以下3个操作：
1：1 x表示如果节点x为白色，则将其染黑。否则对这个节点的所有儿子递归进行相同操作
2：2 x表示将以节点x为root的子树染白。
3：3 x表示查询节点x的颜色
一道很好的树剖题
首先可以把1操作看作单点加(1)，于是我们把每个节点初始赋为(-1)，查询颜色只要看它开始到根的最大后缀就可以了
但是2操作如果直接清(-1)可能它的父亲对子树有影响，所以我们修改完之后把(x)点的权值减去答案(+1)
2操作顺序写反了，然后还对拍什么的调了超久= =
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
const int N = 1e5;
const int INF = 2e7;
#define zrt k << 1
#define yrt k << 1 | 1
using namespace std;
int n,m,size[N + 5],fa[N + 5],son[N + 5],dep[N + 5],top[N + 5],dfn[N + 5],dfn_cnt;
vector <int> d[N + 5];
void dfs1(int u)
{
size[u] = 1;
dep[u] = dep[fa[u]] + 1;
vector <int>::iterator it;
for (it = d[u].begin();it != d[u].end();it++)
{
int v = (*it);
dfs1(v);
size[u] += size[v];
if (size[v] > size[son[u]])
son[u] = v;
}
}
void dfs2(int u,int to)
{
top[u] = to;
dfn[u] = ++dfn_cnt;
if (son[u])
dfs2(son[u],to);
vector <int>::iterator it;
for (it = d[u].begin();it != d[u].end();it++)
{
int v = (*it);
if (v != son[u])
dfs2(v,v);
}
}
struct node
{
int ans,su,ct;
node ()
{
su = ct = 0;
ans = -INF;
}
};
struct Seg
{
node s[N * 4 + 5];
node upd(node x,node y)
{
node k;
k.ans = max(y.ans,y.su + x.ans);
k.su = x.su + y.su;
return k;
}
void build(int k,int l,int r)
{
if (l == r)
{
s[k].su = s[k].ans = -1;
return;
}
int mid = l + r >> 1;
build(zrt,l,mid);
build(yrt,mid + 1,r);
s[k] = upd(s[zrt],s[yrt]);
}
void cha(int k,int l,int r,int z)
{
s[k].su = (r - l + 1) * z;
s[k].ans = z;
s[k].ct = z;
}
void pushdown(int k,int l,int r,int mid)
{
if (s[k].ct != 0)
{
cha(zrt,l,mid,s[k].ct);
cha(yrt,mid + 1,r,s[k].ct);
s[k].ct = 0;
}
}
void add(int k,int l,int r,int x,int z)
{
if (l == r)
{
s[k].su += z;
s[k].ans += z;
return;
}
int mid = l + r >> 1;
pushdown(k,l,r,mid);
if (x <= mid)
add(zrt,l,mid,x,z);
else
add(yrt,mid + 1,r,x,z);
s[k] = upd(s[zrt],s[yrt]);
}
void change(int k,int l,int r,int x,int y,int z)
{
if (l >= x && r <= y)
{
cha(k,l,r,z);
return;
}
int mid = l + r >> 1;
pushdown(k,l,r,mid);
if (x > mid)
change(yrt,mid + 1,r,x,y,z);
else
if (y <= mid)
change(zrt,l,mid,x,y,z);
else
change(zrt,l,mid,x,y,z),change(yrt,mid + 1,r,x,y,z);
s[k] = upd(s[zrt],s[yrt]);
}
node query(int k,int l,int r,int x,int y)
{
if (l >= x && r <= y)
return s[k];
int mid = l + r >> 1;
pushdown(k,l,r,mid);
if (x > mid)
return query(yrt,mid + 1,r,x,y);
else
if (y <= mid)
return query(zrt,l,mid,x,y);
else
return upd(query(zrt,l,mid,x,y),query(yrt,mid + 1,r,x,y));
}
node query(int x)
{
node k;
while (top[x] != 1)
{
k = upd(query(1,1,n,dfn[top[x]],dfn[x]),k);
x = fa[top[x]];
}
k = upd(query(1,1,n,1,dfn[x]),k);
return k;
}
}tree;
int main()
{
scanf("%d%d",&n,&m);
int u,v;
for (int i = 2;i <= n;i++)
{
scanf("%d",&u);
d[u].push_back(i);
fa[i] = u;
}
dfs1(1);
dfs2(1,1);
tree.build(1,1,n);
node k,x;
for (int i = 1;i <= m;i++)
{
scanf("%d%d",&u,&v);
if (u == 1)
tree.add(1,1,n,dfn[v],1);
else
if (u == 2)
{
tree.change(1,1,n,dfn[v],dfn[v] + size[v] - 1,-1);
x = tree.query(v);
tree.add(1,1,n,dfn[v],-x.ans - 1);
}
else
{
k = tree.query(v);
if (k.ans >= 0)
printf("black
");
else
printf("white
");
}
}
return 0;
}