「CF1017G」The Tree

发表于 更新于 分类于

题目链接：https://codeforces.com/problemset/problem/1017/G。

为啥我能把线段树写错然后调一个小时。。

考虑假设没有第二个操作，如何处理第一个操作。

可以反过来想，首先把所有点弄一个权值，初值为$-1$，然后如果对$x$点进行第一种操作，那么就把他的权值加一。

那么如果询问点$x$，只需判断$x$到根节点的前缀和最大值是否大于等于$0$即可。（前缀指$x$为第一个）

所以现在就变成了链上的问题，可以树剖维护。

考虑怎么处理清空操作，首先显然要把子树打成$-1$，但是有个问题就是，可能会有上面传下来的点，也需要清空，那么把那个点减去一个额外的值就好了，这样的话每次前缀和都会消去上面传下来的影响（这部分本身就是需要被清空的）。

复杂度$O(n\log ^2n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define data asd09123jdf02i3h
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int n,q,head[maxn],tot,sz[maxn],hs[maxn],f[maxn],top[maxn],dfn[maxn],dfn_cnt;
 
struct edge{int to,nxt;}e[maxn<<1];
 
void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
 
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
 
struct node {
    int mx,s;
 
    node () {mx=s=0;}
 
    node operator + (const node &r) const {
        node a;
        a.mx=max(r.mx,r.s+mx);
        a.s=s+r.s;
        return a;
    }
};
 
struct segment_tree {
    node t[maxn<<2];
    int tag[maxn<<2];
 
    segment_tree () {
        for(int i=0;i<maxn<<2;i++) tag[i]=inf;
    }
 
    void push(int p,int l,int r,int v) {
        tag[p]=v,t[p].mx=v,t[p].s=v*(r-l+1);
    }
 
    void pushdown(int p,int l,int r) {
        if(tag[p]==inf) return ;
        push(ls,l,mid,tag[p]),push(rs,mid+1,r,tag[p]),tag[p]=inf;
    }
 
    void update(int p) {t[p]=t[ls]+t[rs];}
 
    void modify(int p,int l,int r,int x,int y,int v) {
        if(x<=l&&r<=y) return push(p,l,r,v),void();
        pushdown(p,l,r);
        if(x<=mid) modify(ls,l,mid,x,y,v);
        if(y>mid) modify(rs,mid+1,r,x,y,v);
        update(p);
    }
 
    node query(int p,int l,int r,int x,int y) {
        if(x<=l&&r<=y) return t[p];
        pushdown(p,l,r);
        if(y<=mid) return query(ls,l,mid,x,y);
        if(x>mid) return query(rs,mid+1,r,x,y);
        return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y);
    }
 
    void add(int x) {
        int a=query(1,1,n,x,x).s;
        modify(1,1,n,x,x,a+1);
    }
}T;
 
void dfs(int x,int fa) {
    sz[x]=1;f[x]=fa;
    for(int v,i=head[x];i;i=e[i].nxt) {
        if((v=e[i].to)==fa) continue;
        dfs(v,x),sz[x]+=sz[v];
        if(sz[hs[x]]<sz[v]) hs[x]=v;
    }
}
 
void dfs2(int x) {
    dfn[x]=++dfn_cnt;
    if(hs[f[x]]==x) top[x]=top[f[x]];
    else top[x]=x;
    if(hs[x]) dfs2(hs[x]);
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=f[x]&&e[i].to!=hs[x]) dfs2(e[i].to);
}
 
node get(int x) {
    node ans;ans.mx=-inf;
    while(x) {
        ans=T.query(1,1,n,dfn[top[x]],dfn[x])+ans;
        x=f[top[x]];
    }return ans;
}
 
void cover(int x) {
    T.modify(1,1,n,dfn[x],dfn[x]+sz[x]-1,-1);
    int a=get(x).mx;
    if(a>=0) T.modify(1,1,n,dfn[x],dfn[x],-2-a);
}
 
void query(int x) {
    puts(get(x).mx>=0?"black":"white");
}
 
int main() {
    read(n),read(q);
    for(int i=2,x;i<=n;i++) read(x),ins(i,x),ins(x,i);
    dfs(1,0),dfs2(1);
    for(int i=1;i<=n;i++) T.modify(1,1,n,i,i,-1);
    while(q--) {
        int op,x;read(op),read(x);
        if(op==1) T.add(dfn[x]);
        else if(op==2) cover(x);
        else query(x);
    }
    return 0;
}