CF1017G The Tree
给定一棵树，三种操作：
- 将 \(x\) 染黑，如果其为黑色，那么对子树递归。
- 将 \(x\) 的子树染白。
- 查询 \(x\) 的颜色。
\(n,m\le 10^5\)
Solution
考虑链的情况怎么做。
不考虑操作 \(2\)，假设已知我们进行了若干次操作 \(1\)，如何判定点 \(x\) 的颜色。
假设某个点执行了操作 \(2\) 那么给其权值 \(+1\)，那么考虑从某个 \(u<x\) 处起，如果直到 \(x\) 这一段区间的点权和大于 \(u\to x\) 的距离那么显然就是可以的。
于是条件等价于 \(\exist ~u<x,dis_x-dis_u\le w_x-w_u\) 即 \(\min(w_u-dis_u)\le w_x-dis_x\)
这个做法是可以拓展到树上的。
接下来考虑操作 \(2\)，我们发现我们不好删除之前的操作 \(1\) 的影响。
那么不妨认为操作 \(2\) 带来了独立的影响！我们先清空子树内的增加权值，再给 \(x\) 处增加一个负点权，使得 \(x\) 处的答案刚好被消去即可。设增加的权值为 \(c\)，那么我们希望的是不存在 \(u\) 满足 \(dis_x-dis_u\le w_x-w_u\)
即 \(dis_x-dis_u> w_x-w_u+c,w_u-dis_u>w_x-dis_x+c\)，故 \(c\) 即两者差减 \(1\) 和 \(0\) 取 \(\max\)。
不难发现其正确性，这个算法可以刚好使得 \(2\) 的影响为消去子树贡献。
于是我们只需要支持：查询链上最大值，和子树修改，单点修改，单点查询等操作。
可以通过树链剖分来解决这个问题，复杂度为 \(\mathcal O(m\log^2 n)\)
还有一个非常仙的做法：
考虑对查询进行分块，设块的大小为 \(cnt\)，现在将一个块内的所有查询涉及到的点拿出来建虚树。
这样我们得到了一个大小为 \(cnt\) 的树。
对于每条边，维护边上的点数，和边上白色点的数量。
考虑修改，对于操作 \(1\) 暴力修改即可，注意维护边上的信息。
对于操作 \(2\)，暴力清空子树边上的白色点数量为原点数。
对于查询，直接输出即可。
每处理完一个块之后，我们通过 Dfs 暴力重构这棵树即可。
复杂度为 \(\mathcal O(n\cdot cnt+\frac{n^2}{cnt})\)，平衡可以做到 \(\mathcal O(n\sqrt{n})\)（这里认为 \(n,q\) 同级别）
这里的建虚树是通过 Dfs 建的。
\(Code:\)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int inf = 1e9 + 5 ;
const int N = 2e5 + 5 ;
int n, q, idnex, L[N], R[N], Id[N] ;
int top[N], f[N], dep[N], sz[N], son[N] ;
vector<int> G[N] ;
struct Tr { int w, c, tag, mark ; } tr[N << 2] ;
void dfs1(int x, int fa) {
f[x] = fa, dep[x] = dep[fa] + 1, sz[x] = 1 ;
for(int v : G[x]) {
dfs1(v, x), sz[x] += sz[v] ;
if( sz[v] > sz[son[x]] ) son[x] = v ;
}
}
void dfs2(int x, int high) {
top[x] = high, L[x] = ++ idnex, Id[idnex] = x ;
if(son[x]) dfs2(son[x], high) ;
for(int v : G[x]) if( v ^ son[x] ) dfs2(v, v) ;
R[x] = idnex ;
}
void pushup(int x) { tr[x].w = min(tr[ls(x)].w, tr[rs(x)].w ) ; }
void Col(int x) {
tr[x].mark = 1, tr[x].w = tr[x].c, tr[x].tag = 0 ;
}
void pushmark(int x) {
if( tr[x].mark ) Col(ls(x)), Col(rs(x)), tr[x].mark = 0 ;
int s = tr[x].tag ; tr[x].tag = 0 ;
tr[ls(x)].tag += s, tr[rs(x)].tag += s,
tr[ls(x)].w += s, tr[rs(x)].w += s ;
}
void build(int x, int l, int r) {
if( l == r ) return tr[x].w = tr[x].c = -dep[Id[l]], void() ;
int mid = (l + r) >> 1 ;
build(ls(x), l, mid), build(rs(x), mid + 1, r), pushup(x), tr[x].c = tr[x].w ;
}
void Cover(int x, int l, int r, int ql, int qr) {
if( ql <= l && r <= qr ) return Col(x), void() ;
if( qr < l || r < ql ) return ;
int mid = (l + r) >> 1 ; pushmark(x) ;
Cover(ls(x), l, mid, ql, qr), Cover(rs(x), mid + 1, r, ql, qr), pushup(x) ;
}
void update(int x, int l, int r, int ql, int qr, int k) {
if( ql <= l && r <= qr ) return tr[x].w += k, tr[x].tag += k, void() ;
if( qr < l || r < ql ) return ;
int mid = (l + r) >> 1 ; pushmark(x) ;
update(ls(x), l, mid, ql, qr, k),
update(rs(x), mid + 1, r, ql, qr, k), pushup(x) ;
}
int query(int x, int l, int r, int ql, int qr) {
if( ql <= l && r <= qr ) return tr[x].w ;
if( qr < l || r < ql ) return 0 ;
int mid = (l + r) >> 1 ; pushmark(x) ;
return min(query(ls(x), l, mid, ql, qr), query(rs(x), mid + 1, r, ql, qr)) ;
}
int Q(int x) {
int ans = inf ;
while( x != 1 ) ans = min( ans, query( 1, 1, n, L[top[x]], L[x]) ), x = f[top[x]] ;
ans = min( ans, query(1, 1, n, L[top[x]], L[x]) ) ;
return ans ;
}
void White(int x) {
Cover(1, 1, n, L[x], R[x]) ;
int c = Q(f[x]), w = query(1, 1, n, L[x], L[x]) ;
c = max( 0, c - w - 1 ), update(1, 1, n, L[x], R[x], c) ;
}
void Query(int x) {
int c = Q(f[x]), w = query(1, 1, n, L[x], L[x]) ;
if( c <= w ) puts("black") ;
else puts("white") ;
}
signed main()
{
n = gi() + 1, q = gi() ; int opt, x ;
rep( i, 3, n ) x = gi() + 1, G[x].push_back(i) ;
G[1].push_back(2) ;
dfs1(1, 1), dfs2(1, 1), build(1, 1, n) ;
rep( i, 1, q ) {
opt = gi(), x = gi() + 1 ;
if( opt == 1 ) update(1, 1, n, L[x], R[x], 1) ;
if( opt == 2 ) White(x) ;
if( opt == 3 ) Query(x) ;
}
return 0 ;
}