CF1017G The Tree

发表于 | 阅读数

给定一棵树，维护以下3个操作：

  • 1 $x$表示如果节点$x$为白色，则将其染黑。否则对这个节点的所有儿子递归进行相同操作
  • 2 $x$表示将以节点$x$为$root$的子树染白。
  • 3 $x$表示查询节点$x$的颜色

考虑$1,3$操作。

如果考虑$w[x]$表示往下扩展的儿子,起始都是$-1$。

操作$1$就是把$w[i]+1$,对于操作$2$,就是考虑最大后缀和是否存在$\geq0$

而操作$2$就是清空，考虑把$w[x]=-1$，以及子树都变成$-1$。显然发现一个问题，如果$w[fa[x]]$很大就没办法，那么我们就把$w[x]=-\max{suf[x]}-1$,这样保证了合理性，也保证了实在性，仔细想想运用了树上差分的思想。

由于都是查询都是与根结点的$\max{suf},[1,dfn[x]]$，合并的时候就靠右转移，最大后缀就很舒服了。

代码 
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

struct node
{
    int sum, mx;
};
node merge(node a, node b)
{
    node c;
    c.sum = a.sum + b.sum;
    c.mx = max(b.mx, b.sum + a.mx);
    return c;
}

const int SEN = 1e5 + 10;
struct Segment
{
    node sum[SEN << 2];
    int lazy[SEN << 2];
    void addtag(int pos, int l, int r)
    {
        lazy[pos] = 1;
        sum[pos].mx = -1;
        sum[pos].sum = -(r - l + 1);
    }
    void pushdown(int pos, int l, int r)
    {
        if (lazy[pos])
        {
            int mid = (l + r) >> 1;
            addtag(pos << 1, l, mid);
            addtag(pos << 1 | 1, mid + 1, r);
            lazy[pos] = 0;
        }
    }
    void pushup(int pos)
    {
        sum[pos] = merge(sum[pos << 1], sum[pos << 1 | 1]);
    }
    void update1(int v, int w, int pos, int l, int r)
    {
        if (l == r)
        {
            sum[pos].mx += w;
            sum[pos].sum += w;

            return;
        }
        pushdown(pos, l, r);
        int mid = (l + r) >> 1;
        if (v <= mid)
            update1(v, w, pos << 1, l, mid);
        else
            update1(v, w, pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }
    void update2(int ql, int qr, int pos, int l, int r)
    {
        if (ql > qr)
            return;
        if (ql <= l && r <= qr)
        {
            addtag(pos, l, r);
            return;
        }
        pushdown(pos, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid)
            update2(ql, qr, pos << 1, l, mid);
        if (qr > mid)
            update2(ql, qr, pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }
    node query(int ql, int qr, int pos, int l, int r)
    {
        if (ql <= l && r <= qr)
        {

            return sum[pos];
        }
        pushdown(pos, l, r);
        int mid = (l + r) >> 1;

        if (ql > mid)
            return query(ql, qr, pos << 1 | 1, mid + 1, r);

        else if (qr <= mid)
            return query(ql, qr, pos << 1, l, mid);
        else
            return merge(query(ql, qr, pos << 1, l, mid), query(ql, qr, pos << 1 | 1, mid + 1, r));
    }
} t;

namespace TreePo
{
    int dfn[N], son[N], f[N], dep[N], top[N], out[N], siz[N];
    int tot;
    vector<int> g[N];
    void dfs1(int x, int fa)
    {
        dep[x] = dep[fa] + 1;
        f[x] = fa;
        siz[x] = 1;
        for (int to : g[x])
        {
            if (to == fa)
                continue;
            dfs1(to, x);
            siz[x] += siz[to];
            if (siz[to] > siz[son[x]])
                son[x] = to;
        }
    }
    void dfs2(int x, int fa, int tp)
    {
        dfn[x] = ++tot;
        top[x] = tp;
        if (son[x])
            dfs2(son[x], x, tp);
        for (int to : g[x])
        {
            if (to == fa || to == son[x])
                continue;
            dfs2(to, x, to);
        }
        out[x] = tot;
    }
    int query(int u, int v)
    {
        node res;
        res.sum = 0, res.mx = -1e9;
        while (top[u] != top[v])
        {
            if (dep[top[u]] < dep[top[v]])
                swap(u, v);
            res = merge(t.query(dfn[top[u]], dfn[u], 1, 1, tot), res);
            u = f[top[u]];
        }
        if (dep[u] > dep[v])
            swap(u, v);

        res = merge(t.query(dfn[u], dfn[v], 1, 1, tot), res);
        return res.mx;
    }
    void init(int x)
    {
        dfs1(x, 0);
        dfs2(x, 0, x);

        t.update2(1, tot, 1, 1, tot);
    }
} // namespace TreePo

using namespace TreePo;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
int main()
{
    int n = read(), q = read();
    for (int i = 2; i <= n; i++)
    {
        int x = read();
        g[x].push_back(i);
        g[i].push_back(x);
    }
    init(1);
    for (int i = 1; i <= q; i++)
    {
        int op = read(), x = read();
        if (op == 1)
        {
            t.update1(dfn[x], 1, 1, 1, tot);
        }
        else if (op == 2)
        {
            int o = query(1, x);
            t.update1(dfn[x], -(o + 1), 1, 1, tot);
            t.update2(dfn[x] + 1, out[x], 1, 1, tot);
        }
        else if (op == 3)
        {
            int o = query(1, x);
            if (o >= 0)
                puts("black");
            else
                puts("white");
        }
    }
}