CF1017G The Tree

给定一棵树，三种操作：

将 (x) 染黑，如果其为黑色，那么对子树递归。
将 (x) 的子树染白。
查询 (x) 的颜色。

(n,mle 10^5)

Solution

考虑链的情况怎么做。

不考虑操作 (2)，假设已知我们进行了若干次操作 (1)，如何判定点 (x) 的颜色。

假设某个点执行了操作 (2) 那么给其权值 (+1)，那么考虑从某个 (u<x) 处起，如果直到 (x) 这一段区间的点权和大于 (u o x) 的距离那么显然就是可以的。

于是条件等价于 (exist ~u<x,dis_x-dis_ule w_x-w_u) 即 (min(w_u-dis_u)le w_x-dis_x)

这个做法是可以拓展到树上的。

接下来考虑操作 (2)，我们发现我们不好删除之前的操作 (1) 的影响。

那么不妨认为操作 (2) 带来了独立的影响！我们先清空子树内的增加权值，再给 (x) 处增加一个负点权，使得 (x) 处的答案刚好被消去即可。设增加的权值为 (c)，那么我们希望的是不存在 (u) 满足 (dis_x-dis_ule 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(mlog^2 n))

还有一个非常仙的做法：

考虑对查询进行分块，设块的大小为 (cnt)，现在将一个块内的所有查询涉及到的点拿出来建虚树。

这样我们得到了一个大小为 (cnt) 的树。

对于每条边，维护边上的点数，和边上白色点的数量。

考虑修改，对于操作 (1) 暴力修改即可，注意维护边上的信息。

对于操作 (2)，暴力清空子树边上的白色点数量为原点数。

对于查询，直接输出即可。

每处理完一个块之后，我们通过 Dfs 暴力重构这棵树即可。

复杂度为 (mathcal O(ncdot cnt+frac{n^2}{cnt}))，平衡可以做到 (mathcal O(nsqrt{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 ;
}