Skip to Content
CTRL K

The Tree

Solución

El editorial oficial  menciona usar descomposición Heavy-Light para resolver este problema, pero nunca discute la solución.

En cada nodo, guardamos un factor de propagación. Esencialmente es cuánto negro se ha extendido desde el nodo, o de forma equivalente, el número de operaciones de tipo 1 que se han realizado. Los nodos blancos tienen un factor de propagación de −1-1 y los nodos negros tienen un factor de propagación mayor o igual que cero. Una operación de tipo 1 ahora corresponde directamente a incrementar el factor de propagación de un nodo en 11.

Ahora consideremos la operación 3 (e ignoremos la operación 2 por ahora). ¿Cómo determinamos si un nodo dado es negro? En primer lugar, nótese que si el nodo actual tiene un factor de propagación no negativo, entonces debe ser negro. Si en cambio su padre tuviera un factor de propagación mayor o igual que uno, entonces el nodo también sería negro.

En general, consideremos si se llamó la operación 3 sobre algún nodo uu. Sea vv cualquier nodo que yace en el camino de uu a la raíz. Si la suma de los factores de propagación de uu a vv es no negativa, entonces uu debe ser negro. Esto significa que se han aplicado suficientes operaciones de tipo 1 desde ese nodo (y posiblemente otros nodos en el camino de uu a vv) de modo que uu se volvió negro.

Para las operaciones de tipo 2, podemos limpiar un subárbol dado aprovechando el hecho de que HLD es realmente un tour de Euler específico. Así, un subárbol de un nodo yace en un rango contiguo en la descomposición heavy-light. Podemos limpiar un subárbol usando propagación perezosa y poniendo todos los nodos en un rango a −1-1. Luego, tenemos que ajustar los factores de propagación de todos los nodos por encima de uu, donde se realizó la operación, lo que puede tomar hasta tiempo lineal. Un truco simple es restar un factor de q−1q - 1 del nodo uu, donde qq es el valor de una operación de tipo 3. Esto asegura que cualquier consulta dentro del subárbol de uu evaluará correctamente a blanco después de la actualización.

Nótese que para las operaciones de consulta, necesitamos encontrar la suma de sufijos máxima de cada camino. Esto se puede hacer manteniendo la suma de sufijos máxima así como la suma real en cada nodo del árbol de segmentos.

Implementación

Complejidad temporal: O(n+qlog⁡2n)\mathcal{O}(n + q\log^2n)

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long using pll = pair<ll, ll>;
#define FF first
#define SS second
 
const int MAXN = 1e5 + 1;
 
int N, Q;
vector<int> G[MAXN];
 
// Segment Tree:
namespace sgt {
pll T[MAXN * 4];   // {value, sum}
bool L[MAXN * 4];  // set tag
 
pll merge(pll l, pll r) {
	if (l.SS == -LLONG_MAX) { return r; }
	if (r.SS == -LLONG_MAX) { return l; }
	return {max(l.FF + r.SS, r.FF), l.SS + r.SS};
}
 
void build(int t = 1, int tl = 0, int tr = N - 1) {
	if (tl == tr) {
		T[t].FF = T[t].SS = -1;
		return;
	}
 
	int tm = (tl + tr) >> 1;
	build(t << 1, tl, tm);
	build(t << 1 | 1, tm + 1, tr);
	T[t] = merge(T[t << 1], T[t << 1 | 1]);
}
 
void pushdown(int t, int tl, int tr) {
	if (!L[t]) { return; }
	int tm = (tl + tr) >> 1;
	T[t << 1] = {-1, -(tm - tl + 1)};
	T[t << 1 | 1] = {-1, -(tr - tm)};
	L[t << 1] = L[t << 1 | 1] = 1;
	L[t] = 0;
}
 
void update_range(int l, int r, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return; }
	if (l <= tl && tr <= r) {
		T[t] = {-1, -(tr - tl + 1)};
		L[t] = 1;
		return;
	}
	pushdown(t, tl, tr);
 
	int tm = (tl + tr) >> 1;
	update_range(l, r, t << 1, tl, tm);
	update_range(l, r, t << 1 | 1, tm + 1, tr);
	T[t] = merge(T[t << 1], T[t << 1 | 1]);
}
 
void update_point(int i, int v, int t = 1, int tl = 0, int tr = N - 1) {
	if (tl == tr) {
		T[t].FF += v;
		T[t].SS += v;
		return;
	}
	pushdown(t, tl, tr);
 
	int tm = (tl + tr) >> 1;
	if (i <= tm) {
		update_point(i, v, t << 1, tl, tm);
	} else {
		update_point(i, v, t << 1 | 1, tm + 1, tr);
	}
	T[t] = merge(T[t << 1], T[t << 1 | 1]);
}
 
pll query(int l, int r, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return {-LLONG_MAX, -LLONG_MAX}; }
	if (l <= tl && tr <= r) { return T[t]; }
	pushdown(t, tl, tr);
 
	int tm = (tl + tr) >> 1;
	return merge(query(l, r, t << 1, tl, tm), query(l, r, t << 1 | 1, tm + 1, tr));
}
}  // namespace sgt
 
// Heavy-Light Decomposition:
namespace hld {
int par[MAXN], hvy[MAXN], dep[MAXN], root[MAXN], lpos[MAXN], rpos[MAXN];
 
// initialize par, hvy, dep
int dfs1(int u) {
	int sze = 1, msub = 0;
	for (int v : G[u]) {
		par[v] = u;
		dep[v] = dep[u] + 1;
		int sub = dfs1(v);
		if (sub > msub) { hvy[u] = v, msub = sub; }
		sze += sub;
	}
	return sze;
}
 
// initialize root, lpos, rpos
void dfs2(int u) {
	static int t = -1;
 
	lpos[u] = ++t;
	if (hvy[u] != -1) {
		root[hvy[u]] = root[u];
		dfs2(hvy[u]);
	}
	for (int v : G[u])
		if (v != hvy[u]) {
			root[v] = v;
			dfs2(v);
		}
	rpos[u] = t;
}
 
void init() {
	fill_n(hvy, MAXN, -1);
	par[1] = -1;
	dep[1] = 0;
	dfs1(1);
	root[1] = 1;
	dfs2(1);
	sgt::build();
}
 
pll query(int u) {
	pll ans = {-LLONG_MAX, -LLONG_MAX};
	while (u != -1) {
		ans = sgt::merge(sgt::query(lpos[root[u]], lpos[u]), ans);
		u = par[root[u]];
	}
	return ans;
}
}  // namespace hld
 
int main() {
	cin >> N >> Q;
	for (int i = 2; i <= N; i++) {
		int p;
		cin >> p;
		G[p].push_back(i);
	}
 
	hld::init();
	while (Q--) {
		int t, u;
		cin >> t >> u;
		if (t == 1) {
			sgt::update_point(hld::lpos[u], 1);
		} else if (t == 2) {
			sgt::update_range(hld::lpos[u], hld::rpos[u]);
			int q = hld::query(u).FF;
			if (q >= 0) { sgt::update_point(hld::lpos[u], -q - 1); }
		} else if (t == 3) {
			if (hld::query(u).FF >= 0) {
				cout << "black\n";
			} else {
				cout << "white\n";
			}
		}
	}
}
Fundamentos